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左右子树的范围都是连续的。中间就是root。
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 };
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 };
Leetcode | Construct Binary Tree from Inorder and (Preorder or Postorder) Traversal,布布扣,bubuko.com
Leetcode | Construct Binary Tree from Inorder and (Preorder or Postorder) Traversal
原文：http://www.cnblogs.com/linyx/p/3734763.html