• 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)