【Leetcode】515.在每个树行中找最大值

515.在每个树行中找最大值

题目

您需要在二叉树的每一行中找到最大的值。

示例：
输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

方法一（BFS)

在广度优先遍历的时候用变量size记录每一层的节点个数，在遍历这一层时找到此层中的最大值，添加到结果数组中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> largestValues(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null)
        return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    //while循环代表整个BFS的逻辑
    while(!queue.isEmpty()){
        //当前层节点数量
        int size = queue.size();
        int max = Integer.MIN_VALUE;
        //for循环表示每一层的遍历
        for(int i = 0 ; i < size; i++){
            TreeNode node = queue.poll();
            max = Math.max(max, node.val);
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
        }
        res.add(max);
    }
    return res;
}

方法二（DFS)

在进行深度优先遍历时，每次遍历到新的一层时，我们都将现在遍历到的这个该层节点加入到结果数组res中（但其实上这个节点并不一定是该层最大的，不过没关系，我们之后再更新它）。之后再遍历到同在这一层的其他节点时再进行更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> largestValues(TreeNode root) {
        dfs(root, 1);
        return res;
    }
    public void dfs(TreeNode root, int level){
        if(root == null)
            return;
        //如果是第一次来到第level层，那就先把当前遍历到达level层的这个节点加入到结果数组res中
        if(level == res.size() + 1)
            res.add(root.val);
        //之后再遍历到同在level层的其他节点时对res中的值进行更新
        else{
            int max = Math.max(res.get(level - 1), root.val);
            res.set(level - 1, max);
        }
        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}