LeetCode 106 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.

Diffculty Medium

Similar Problems [LeetCode 105] Construct Binary Tree from Preorder and Inorder Traversal M

Analysis

中序序列仍然是以根节点划分为左右两边，而后序序列的特点则是根在最后，然后在跟前面的那部分中，前面部分是左子树，后面的部分是右子树。所以其实我们就是把上一题给反过来了。这题我们将后序序列的指针全局化，这样我们可以先建好右子树，再建左子树，而指针只要顺序从后向前就行了。

Solutions

class Solution {
public:
    int postEnd;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        postEnd = postorder.size() - 1;
        if(inorder.size() == 0 || postorder.size() == 0) return nullptr;
        return helper(postorder, inorder, 0, inorder.size() - 1);
    }
    TreeNode* helper(vector<int>& postorder, vector<int>& inorder, int inStart, int inEnd){
        if(postEnd < 0 || inStart > inEnd){
            return nullptr;
        }
        TreeNode *root = new TreeNode(postorder[postEnd--]);
        int inMid = 0;
        for(int i = inStart ; i <= inEnd; i++){   // 找到根在中序序列中的位置
            if(inorder[i] == root->val){
                inMid = i;
                break;
            }
        }
        root->right = helper(postorder, inorder, inMid + 1, inEnd);  // 建右子树
        root->left = helper(postorder, inorder, inStart, inMid - 1); // 建左子树
        return root;
    }
};

References