1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
HashMap<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length
indexMap = new HashMap<>();
for(int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n-1, 0, n-1);
}
private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
if (preorderLeft > preorderRight) {
return null;
}
int preorderRoot = preorderLeft;
int inorderRoot = indexMap.get(preorder[preorderLeft])
TreeNode root = new TreeNode(preorder[preorderLeft]);
int sizeLeftSubTree = inorderRoot - inorderLeft;
root.left = myBuildTree(preorder,inorder, preorderLeft+1, preorderLeft+sizeLeftSubTree, inorderLeft, inorderRoot-1);
root.right = myBuildTree(preorder,inorder, preorderLeft+sizeLeftSubTree+1, preorderRight, inorderRoot+1, inorderRight);
return root;
}
}
|