FInd Largest Value in Each Tree Row

Problem

You need to find the largest value in each row of a binary tree.

Example:
Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

Solution

Pre-order DFS Solution: O(n) time, O(n) size

public class Solution {

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res, 0);
        return res;
    }

    private void helper(TreeNode node, List<Integer> res, int depth) {
        if (node == null) return;
        if (depth >= res.size()) res.add(node.val);
        else res.set(depth, Math.max(node.val, res.get(depth)));
        helper(node.left, res, depth + 1);
        helper(node.right, res, depth + 1);
    }
}

BFS Solution: O(n) time, O(n) space

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size(), max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                max = Math.max(max, node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            res.add(max);
        }
        return res;
    }
}

Analysis

A typical traversal solution by recording the current depth
In DFS solution, we pass the depth as a parameter in helper() method
If we reach a new depth, which means depth >= res.size(), we add the current node.val
Otherwise, we use res.set() to update the max value
Then we traversal the tree in pre-order with increased depth + 1

In the BFS solution, we use a for loop to get max in same level
Therefore, we need to get the current node with q.poll() and add node.left and node.right inside for loop
Then after the loop, we will get the max value and add the max to our res