105 Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

1. Question

Given preorder and inorder traversal of a tree, construct the binary tree.

2. Implementation

(1) Recursion
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public TreeNode buildTree(int[] preorder, int[] inorder) {
12
if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
13
return null;
14
}
15
16
Map<Integer, Integer> map = new HashMap<>();
17
for (int i = 0; i < inorder.length; i++) {
18
map.put(inorder[i], i);
19
}
20
21
return constructTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
22
}
23
24
public TreeNode constructTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {
25
if (preStart > preEnd || inStart > inEnd) {
26
return null;
27
}
28
29
TreeNode root = new TreeNode(preorder[preStart]);
30
31
int index = map.get(root.val);
32
33
root.left = constructTree(preorder, preStart + 1, preStart + (index - inStart), inorder, inStart, index - 1, map);
34
root.right = constructTree(preorder, preStart + 1 + (index - inStart), preEnd, inorder, index + 1, inEnd, map);
35
return root;
36
}
37
}
Copied!
(2) Iteration
1
Copied!

3. Time & Space Complexity

Recursion: 时间复杂度O(n^2), 当树是skewed的时候,平均时间是O(nlogn), 空间复杂度O(n),因为用了map