Leetcode | Construct Binary Tree from Inorder and (Preorder or Postorder) Traversal

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
차례로 구축하다.
사고방식은 바로preorder는 뿌리 결점을 포지셔닝할 수 있고inorder는 좌우 트리의 수치 범위를 포지셔닝할 수 있다.
1.preorder에서 뿌리 결점 얻기;preorder 첫 번째 점 지우기;
2. 먼저 왼쪽 나무를 세우기;우자나무 재건하기;
한 구간을 통해 좌우 트리의 수치 범위를 표시한다.inorder 좌우 나무의 범위가 연속적이기 때문이다.가운데가 루트야.

 1 class Solution {

 2 public:

 3     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

 4         return recursive(preorder, inorder, 0, inorder.size() - 1);

 5     }

 6     

 7     TreeNode* recursive(vector<int> &preorder, vector<int> &inorder, int s, int e) {

 8         if (s > e) return NULL;

 9         if (preorder.empty()) return NULL;

10         TreeNode *root = new TreeNode(preorder.front());

11         preorder.erase(preorder.begin());

12         

13         int i = s;

14         for (; i <= e && inorder[i] != root->val; ++i);

15         root->left = recursive(preorder, inorder, s, i - 1);

16         root->right = recursive(preorder, inorder, i + 1, e);

17     }

18 };

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
위와 유사하다.두 가지가 다르다.
1.postorder, 마지막 원소는 뿌리 결점이다.
2. 먼저 오른쪽 트리를 구축하고 왼쪽 트리를 구축한다.

 1 class Solution {

 2 public:

 3     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

 4         return recursive(postorder, inorder, 0, inorder.size() - 1);

 5     }

 6     

 7     TreeNode* recursive(vector<int> &postorder, vector<int> &inorder, int s, int e) {

 8         if (s > e) return NULL;

 9         if (postorder.empty()) return NULL;

10         TreeNode *root = new TreeNode(postorder.back());

11         postorder.pop_back();

12         

13         int i = s;

14         for (; i <= e && inorder[i] != root->val; ++i);

15         root->right = recursive(postorder, inorder, i + 1, e);

16         root->left = recursive(postorder, inorder, s, i - 1);

17     }

18 };