05 August 2008
在二叉树中找每一行的最大值
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 1. 深度优先搜索(DFS) --
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> list = new ArrayList<>();
dfs(root, list, 0);
return list;
}
public void dfs(TreeNode node, List<Integer> list, int level) {
if (node == null) return;
if (list.size() == level) {
list.add(node.val);
} else {
list.set(level, Math.max(list.get(level), node.val));
}
dfs(node.left, list, level+1);
dfs(node.right, list, level+1);
}
}
BFS
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
/**
* 2. 广度优先搜索(BFS) -- 按层级遍历
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
max = Math.max(node.val, max);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
list.add(max);
}
return list;
}
}