[LeetCode] 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.

思路：

Binary tree一共3种访问顺序：preorder, inorder, postorder。这道题目的推广就是给定一个binary tree的两种访问顺序，重构该binary tree。这类题目给定的两个排序中，如果包括了inorder，且没有重复元素，就非常好解了。解这类题有两个关键点：

1. 在inorder中寻找root的位置，从而从序列中分割出左右子树。

Inorder:     left subtree | root | right subtree

Preorder:   root | left subtree | right subtree

Postorder: left subtree | right subtree | root 

可见root是preorder序列的第一个节点，也是postorder的最后一个节点。所以给定这两个序列的任意一个我们即知道了root->val。通过搜索inorder序列，可以定位root所在的位置，从而也得到了left subtree和right subtree的节点数。

2. 递归构建

当root，left/right subtree都确定后

root->left = construct(inorder(left subtree), preorder(left subtree))

root->right = construct(inorder(right subtree), preorder(right subtree))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { if(preorder.size()!=inorder.size()) return NULL; int n = preorder.size(); return buildBT(preorder, inorder, 0, n-1, 0, n-1); } TreeNode *buildBT(vector<int> &preorder, vector<int> &inorder, int s1, int e1, int s2, int e2) { if(s1>e1 || s2>e2) return NULL; TreeNode *root = new TreeNode(preorder[s1]); int rootIndex = -1; // root index in inorder for(int i=s2; i<=e2; i++) { if(inorder[i]==root->val) { rootIndex = i; } } if(rootIndex==-1) return NULL; int leftTreeSize = rootIndex - s2; int rightTreeSize = e2 - rootIndex; root->left = buildBT(preorder, inorder, s1+1, s1+leftTreeSize, s2, rootIndex-1); root->right = buildBT(preorder, inorder, e1-rightTreeSize+1, e1, rootIndex+1, e2); return root; } };