106

106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

 

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

 

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

Companies:
Microsoft, Google, Amazon, Shopee

Related Topics:
Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Similar Questions:

• Construct Binary Tree from Preorder and Inorder Traversal (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(H)
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        function<TreeNode*(int, int, int, int)> build = [&](int is, int ie, int ps, int pe) -> TreeNode* {
            if (is == ie) return NULL;
            auto n = new TreeNode(postorder[pe - 1]);
            int mid = find(begin(inorder) + is, begin(inorder) + ie, n->val) - begin(inorder);
            n->left = build(is, mid, ps, ps + mid - is);
            n->right = build(mid + 1, ie, ps + mid - is, pe - 1);
            return n;
        };
        return build(0, inorder.size(), 0, postorder.size());
    }
};

Or use a map to store the value to index pairs

// OJ: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> m;
        for (int i = 0; i < inorder.size(); ++i) m[inorder[i]] = i;
        function<TreeNode*(int, int, int, int)> build = [&](int is, int ie, int ps, int pe) -> TreeNode* {
            if (is == ie) return NULL;
            auto n = new TreeNode(postorder[pe - 1]);
            int mid = m[n->val];
            n->left = build(is, mid, ps, ps + mid - is);
            n->right = build(mid + 1, ie, ps + mid - is, pe - 1);
            return n;
        };
        return build(0, inorder.size(), 0, postorder.size());
    }
};

Solution 2.

We traverse the tree in pre-order from right to left (normal pre-order is from left to right), i.e. from the last to the first elements of postorder.

if (inorder[inorderIndex] != node->val) node->right = build(node); 

If inorder[inorderIndex] != node->val, it means that there are some right children of this current node. postorder[postorderIndex] is the direct right child of node, while inorder[inorderIndex] is the rightmost child of node.

We keep appending right children until inorder[inorderIndex] == node->val which means that node doesn't have any right children.

Now we can decrement inorderIndex.

if (!end || inorder[inorderIndex] != end->val) node->left = build(end);

    0
  /
1
  \ 
    2
  / 
3
inorder: [1,3,2,0]
postorder: [3,2,1,0]

Node 0's end is NULL.
Node 2's end is node 1.
Node 3's end is node 1.
Node 1's end is NULL.

end points to the closest ancester node that node is a right child of end.

If inorder[inorderIndex] == end->val, it means that we've exhausted the right subtree of node end -- no more left children for the current node.
Otherwise, we build tree as the left subtree of the current node.

// OJ: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
// Ref: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/34782/My-recursive-Java-code-with-O(n)-time-and-O(n)-space/33107
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int inorderIndex = inorder.size() - 1, postorderIndex = postorder.size() - 1;
        function<TreeNode*(TreeNode*)> build = [&](TreeNode *end) -> TreeNode* {
            if (postorderIndex < 0) return NULL;
            auto node = new TreeNode(postorder[postorderIndex--]);
            if (inorder[inorderIndex] != node->val) node->right = build(node); 
            --inorderIndex;
            if (!end || inorder[inorderIndex] != end->val) node->left = build(end);
            return node;
        };
        return build(NULL);
    }
};