106 - Construct Binary Tree from Inorder and Postorder Traversal

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.

Hide Tags

Tree Array Depth-first Search

Hide Similar Problems

(M) Construct Binary Tree from Preorder and Inorder Traversal

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

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

在讨论区看到一个直接用 stack 迭代实现的，有点意思：
https://leetcode.com/discuss/6334/here-is-my-o-n-solution-is-it-neat

/**
* 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>& inorder, vector<int>& postorder) {
        return build(inorder, 0, inorder.size(),
                        postorder, 0, postorder.size());
    }
   
    TreeNode* build(vector<int>& inorder, int is, int ie,
                    vector<int>& postorder, int ps, int pe) {
        TreeNode* root = NULL;
        if(ps<pe)
        {
            int val = postorder[pe-1];              //last 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, postorder, ps, ps+(ii-is));
            root->right = build(inorder, ii+1, ie, postorder, ps+(ii-is), pe-1);
        }
        return root;
    }
};
12 ms.