105 - Construct Binary Tree from Preorder and Inorder 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.

Hide Tags

Tree Array Depth-first Search

Hide Similar Problems

(M) Construct Binary Tree from Inorder and Postorder Traversal

关键在于，Preorder 的各级root，就在vector 中该子树段落的段首。
定位了root之后，回到 Inorder 里找到相应的位置，就可以把它的左子右子 Inorder 分开了
进而根据Inorder的长度，将 Preorder 也分开，这样就可以递归进入下一层了。
当 Preorder 递归到首末重叠，就到了叶子节点的左右子了，返回 NULL 即可。

一个有趣的现象是，在 Inorder 里查找当前 root 的时候，++ (36 ms) 向上找的效率明显低于 – (12 ms)，
有可能是测试 case 里的分布不平均，右子残缺的情况比左子多。（for 循环 ++/-- 之间的效率差别应该没这么大）

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(inorder, 0, inorder.size(),
                        preorder, 0, preorder.size());
    }
   
    TreeNode* build(vector<int>& inorder, int is, int ie,
                    vector<int>& preorder, int ps, int pe) {
        TreeNode* root = NULL;
        if(ps<pe)
        {
            int val = preorder[ps];                 //first is root
            root = new TreeNode(val);
   
            //faster than doing ++ from is to ie, but why??
            int ii=ie-1;
            while(ii>=is && val != inorder[ii])
                ii--;

            root->left = build(inorder, is, ii, preorder, ps+1, ps+1+(ii-is));
            root->right = build(inorder, ii+1, ie, preorder, ps+1+(ii-is), pe);
        }
        return root;
    }
};
12 ms.