106. Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution | Easy Approach

Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution 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.

Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    unordered_map<int, int> inToIndex;

    for (int i = 0; i < inorder.size(); ++i)
      inToIndex[inorder[i]] = i;

    return build(inorder, 0, inorder.size() - 1, postorder, 0,
                 postorder.size() - 1, inToIndex);
  }

 private:
  TreeNode* build(const vector<int>& inorder, int inStart, int inEnd,
                  const vector<int>& postorder, int postStart, int postEnd,
                  const unordered_map<int, int>& inToIndex) {
    if (inStart > inEnd)
      return nullptr;

    const int rootVal = postorder[postEnd];
    const int rootInIndex = inToIndex.at(rootVal);
    const int leftSize = rootInIndex - inStart;

    TreeNode* root = new TreeNode(rootVal);
    root->left = build(inorder, inStart, rootInIndex - 1, postorder, postStart,
                       postStart + leftSize - 1, inToIndex);
    root->right = build(inorder, rootInIndex + 1, inEnd, postorder,
                        postStart + leftSize, postEnd - 1, inToIndex);
    return root;
  }
};

Java

 class Solution {
  public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer, Integer> inToIndex = new HashMap<>();

    for (int i = 0; i < inorder.length; ++i)
      inToIndex.put(inorder[i], i);

    return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inToIndex);
  }

  TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd,
                 Map<Integer, Integer> inToIndex) {
    if (inStart > inEnd)
      return null;

    final int rootVal = postorder[postEnd];
    final int rootInIndex = inToIndex.get(rootVal);
    final int leftSize = rootInIndex - inStart;

    TreeNode root = new TreeNode(rootVal);
    root.left = build(inorder, inStart, rootInIndex - 1, postorder, postStart,
                      postStart + leftSize - 1, inToIndex);
    root.right = build(inorder, rootInIndex + 1, inEnd, postorder, postStart + leftSize,
                       postEnd - 1, inToIndex);
    return root;
  }
}

Python

class Solution:
  def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    inToIndex = {num: i for i, num in enumerate(inorder)}

    def build(inStart: int, inEnd: int, postStart: int, postEnd: int) -> Optional[TreeNode]:
      if inStart > inEnd:
        return None

      rootVal = postorder[postEnd]
      rootInIndex = inToIndex[rootVal]
      leftSize = rootInIndex - inStart

      root = TreeNode(rootVal)
      root.left = build(inStart, rootInIndex - 1,  postStart,
                        postStart + leftSize - 1)
      root.right = build(rootInIndex + 1, inEnd,  postStart + leftSize,
                         postEnd - 1)
      return root

    return build(0, len(inorder) - 1, 0, len(postorder) - 1)

Watch Tutorial

Checkout more Solutions here