-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathLeetCode105.java
More file actions
107 lines (99 loc) · 3.95 KB
/
LeetCode105.java
File metadata and controls
107 lines (99 loc) · 3.95 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package problems;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
/**
* 递归
*/
public class LeetCode105 {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if(preLen != inLen) {
throw new RuntimeException("Incorrect input data");
}
Map<Integer, Integer> map = new HashMap<>(preLen);
// 用空间换时间，快速知道元素对应的下标位置
for (int i = 0; i < inLen; i++) {
map.put(inorder[i], i);
}
return buildTree(preorder, 0, preLen - 1, map, 0, inLen - 1);
}
/**
* @param preorder 前序遍历序列
* @param preLeft 前序遍历序列子区间的左边界，可以取到
* @param preRight 前序遍历序列子区间的右边界，可以取到
* @param map 在中序遍历序列里，数值与下标的对应关系
* @param inLeft 中序遍历序列子区间的左边界，可以取到
* @param inRight 中序遍历序列子区间的右边界，可以取到
* @return
*/
private TreeNode buildTree(int[] preorder, int preLeft, int preRight, Map<Integer, Integer> map, int inLeft, int inRight) {
if(preLeft > preRight || inLeft > inRight) {
return null;
}
int rootValue = preorder[preLeft];
TreeNode root = new TreeNode(rootValue);
int pIndex = map.get(rootValue);
root.left = buildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);
root.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);
return root;
}
}
/**
* 迭代
*/
class LeetCode105_1 {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.length; i++) {
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
}
class LeetCode105_2 {
private Map<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 preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if(preorder_left > preorder_right) {
return null;
}
// 前序遍历第一个节点就是根节点
int preorder_root = preorder_left;
int inorder_root = indexMap.get(preorder[preorder_root]);
TreeNode root = new TreeNode(preorder[preorder_root]);
// 得到左子树的节点数目
int size_left_subtree = inorder_root - inorder_left;
root.left = MyBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
root.right = MyBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
}