515. Find Largest Value in Each Tree Row

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

Input: root = [1,2,3]
Output: [1,3]

Constraints:

• The number of nodes in the tree will be in the range [0, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Code

BFS

class Solution {
    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 size = queue.size();
            int large = Integer.MIN_VALUE;
            
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                large = Math.max(large, node.val);

                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }

            res.add(large);
        }

        return res;
    }
}

DFS

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        
        helper(root, res, 0);
        
        return res;
    }
    
    private void helper(TreeNode root, List<Integer> res, int depth){
        if(root == null){
            return;
        }

        if(depth == res.size()){
            res.add(root.val);
        } 
            
        res.set(depth, Math.max(res.get(depth), root.val));
        
        helper(root.left, res, depth + 1);
        helper(root.right, res, depth + 1);
    }
}