剑指offer_044 二叉树每层的最大值

题目：

给定一棵二叉树的根节点?root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
? ? ? ? ? 1
? ? ? ? ?/ \
? ? ? ? 3 ? 2
? ? ? ?/ \ ? \ ?
? ? ? 5 ? 3 ? 9?

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
? ? ? ? ? 1
? ? ? ? ?/ \
? ? ? ? 2 ? 3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释: ? ? ?
?? ? ? ? ? 1?
?? ? ? ? ? ?\
?? ? ? ? ? ? 2 ? ??

示例5：

输入: root = []
输出: []

提示：

二叉树的节点个数的范围是 [0,104]
-231?<= Node.val <= 231?- 1

代码一：广度优先遍历

class Solution {

    public List<Integer> largestValues(TreeNode root) {
        
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> q =new LinkedList<>();
        q.offer(root);
        // count是用来记录每层的节点数
        int count = q.size();
        int res = Integer.MIN_VALUE;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
            count--;
            res = Math.max(res, node.val);
            // 该层结束
            if (count == 0) {
                count = q.size();
                list.add(res);
                res = Integer.MIN_VALUE;
                
            }
        }
        return list;
    }


}

代码二：深度优先遍历

  // DFS
    class Solutions {
        List<Integer> list;
        public List<Integer> largestValues(TreeNode root) {
            list = new ArrayList<Integer>();
            // 深度一开始设为零以为 List 集合的下标是从0开始的，方便后面更新每层的最大值
            dfs(root, 0);
            return list;
        }
        public void dfs(TreeNode root, int depth) {
            if(root == null) {
                return;
            }
            // 更新最大值
            if(list.size() < depth + 1) {
                // 先把每一层最左边的加进来
                list.add(root.val);
            } else {
                // 更新每层的最大值
                int val = list.get(depth);
                list.set(depth, Math.max(val, root.val));
            }

            dfs(root.left, depth + 1);
            dfs(root.right, depth + 1);
        }
    }

解题思路：

这部分题还是比较烦人的，又可以深度又可以广度，深度递归难以理解，广度太长代码难写。不过当你理解一道题以后，就可以举一反三，一骑绝尘啦。

注意：?

按时吃饭。

参考链接：

力扣