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

题目描述

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

输入输出

1
2
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

基本思路

深搜：定义一个currHeight标记目前遍历的高度 更新最大值 时复$O(n)$ 空复$O(height)$

广搜：层序遍历 对每一层的所有节点大小作比较 时复$O(n)$ 空复$O(n)$

java实现

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
36
37
38
39
40
41
42
43
44
45
46
// 深搜
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;
        dfs(result, root, 0);
        return result;
    }

    public void dfs(List<Integer> res, TreeNode root, int currHeight){
        if(currHeight == res.size()){
            res.add(root.val);
        }else{
            res.set(currHeight, Math.max(res.get(currHeight), root.val));
        }
        if(root.left != null){
            dfs(res, root.left, currHeight+1);
        }
        if(root.right != null){
            dfs(res, root.right, currHeight+1);
        }
    }
}

// 广搜
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;
        List<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int maxVal = Integer.MIN_VALUE;
            int currLevel = queue.size();
            for(int i = 1; i <= currLevel; i++) {
                TreeNode temp = queue.poll();
                maxVal = Math.max(maxVal, temp.val);
                if(temp.left != null) queue.offer(temp.left);
                if(temp.right != null) queue.offer(temp.right);
            }
            result.add(maxVal);
        }
        return result;
    }
}