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

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

 

【BFS 层次遍历】

class Solution {

    // 层次遍历 9:15 9:22

    List<Integer> ans = new ArrayList();

    public void bfs(TreeNode node){
        if(node == null) return;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(node);
        while(!queue.isEmpty()){
            int k = queue.size();
            int max = Integer.MIN_VALUE;
            while(k-- > 0){
                TreeNode top = queue.poll();
                max = Math.max(max, top.val);
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
            }
            ans.add(max);
        }
    }

    public List<Integer> largestValues(TreeNode root) {
        bfs(root);
        return ans;
    }
}

【DFS】用一个参数来记录层信息

class Solution {

    // DFS 9:38

    List<Integer> ans = new ArrayList();

    public void dfs(TreeNode node, int t){
        if(node == null) return;
        if(ans.size() == t) ans.add(node.val);
        else ans.set(t, Math.max(ans.get(t), node.val));
        dfs(node.left, t + 1);
        dfs(node.right, t + 1);
    }

    public List<Integer> largestValues(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
}