LeetCode Solutions

			

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;
  }
};

			

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;
  }
}

			

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)