力扣515
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
也就是找每行的最大值
思路一：bfs层次遍历每行嘛，找最大值并加入res
思路二：dfs深度优先，res中记录每行的最大值，通过level回溯参数定位现在是第几行，更新res.set(level - 1, max(res.get(level - 1), 当前节点值));
bfs写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelMax = Integer.MIN_VALUE;
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode cur = queue.poll();
levelMax = Math.max(levelMax, cur.val);
if(cur.left != null) queue.offer(cur.left);
if(cur.right != null) queue.offer(cur.right);
}
res.add(levelMax);
}
return res;
}
|
dfs写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private List<Integer> res = new ArrayList<>();
public List<Integer> largestValues2(TreeNode root) {
dfs(root, 1);
return res;
}
public void dfs(TreeNode node, int level){
if (node == null) return ;
if (level == res.size() + 1){
res.add(node.val);
}else{
res.set(level - 1, Math.max(res.get(level - 1), node.val));
}
dfs(node.left, level + 1);
dfs(node.right, level + 1);
}
|
dfs确实比bfs快，由4ms提高到1ms，文德提出的这个dfs解法还是不错的
其他树的题目点击这里
