05 August 2008
给定两棵二叉搜索树 root1 和 root2，返回一个列表，该列表包含两棵树中按升序排序的所有整数。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
List<Integer> result = new ArrayList<>();
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
preOrderTraversal(root1);
preOrderTraversal(root2);
Collections.sort(result);
return result;
}
public void preOrderTraversal(TreeNode root) {
if(root == null) return;
result.add(root.val);
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
}
Stack
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
class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return null;
List<Integer> list = new ArrayList<>();
parallelInorder(root1, root2, list);
return list;
}
public void parallelInorder(TreeNode root1, TreeNode root2, List<Integer> list) {
Stack<TreeNode> st1 = new Stack();
Stack<TreeNode> st2 = new Stack();
while (root1 != null || root2 != null || !st1.isEmpty() || !st2.isEmpty()) {
while (root1 != null) {
st1.push(root1);
root1 = root1.left;
}
while (root2 != null) {
st2.push(root2);
root2 = root2.left;
}
int a = st1.isEmpty() ? Integer.MAX_VALUE : st1.peek().val;
int b = st2.isEmpty() ? Integer.MAX_VALUE : st2.peek().val;
if (a < b) {
root1 = st1.pop();
list.add(root1.val);
root1 = root1.right;
} else {
root2 = st2.pop();
list.add(root2.val);
root2 = root2.right;
}
}
}
}