105. Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution

Minimum Cost to Merge Stones
Share:

Construct Binary Tree from Preorder and Inorder Traversal Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

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

Example 2:

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

Constraints:

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

Construct Binary Tree from Preorder and Inorder Traversal Solutions

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

C++

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

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

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

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

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

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

Java

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

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

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

  private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart,
                         int inEnd, Map<Integer, Integer> inToIndex) {
    if (preStart > preEnd)
      return null;

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

    TreeNode root = new TreeNode(rootVal);
    root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart,
                      rootInIndex - 1, inToIndex);
    root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootInIndex + 1, inEnd,
                       inToIndex);

    return root;
  }
}

Python

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

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

      rootVal = preorder[preStart]
      rootInIndex = inToIndex[rootVal]
      leftSize = rootInIndex - inStart

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

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

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x