Find Largest Value in Each Tree Row

This approach traverses the tree level by level using a queue. For each level, it iterates through all the nodes at that level to find the maximum value, then adds it to the result list. This is a very intuitive method for problems involving tree levels.

• Initialize an empty list result.
• If the root is null, return the empty list.
• Create a Queue and add the root node.
• While the queue is not empty:
  • Get the number of nodes in the current level, levelSize = queue.size().
  • Initialize a variable maxInLevel to Integer.MIN_VALUE.
  • Loop levelSize times:
    • Dequeue a node currentNode.
    • Update maxInLevel with the maximum of its current value and currentNode.val.
    • Enqueue the left and right children of currentNode if they are not null.
  • Add maxInLevel to the result list.
• Return result.

We can solve this problem by performing a level order traversal of the tree, which is naturally implemented using a Breadth-First Search (BFS) algorithm with a queue.

The core idea is to process the tree one level at a time. We start by putting the root node in a queue. Then, we enter a loop that continues as long as the queue is not empty. In each iteration of this outer loop, we are processing a single level. We first determine the number of nodes on the current level by checking the queue's size. We then iterate exactly that many times, dequeueing one node at a time. While processing the nodes of a level, we keep track of the maximum value seen so far. After the inner loop finishes, we have the largest value for that level, which we add to our result list. We also add the children of each processed node to the queue, which sets up the next level for the subsequent iteration of the outer loop.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int maxInLevel = Integer.MIN_VALUE;

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                maxInLevel = Math.max(maxInLevel, currentNode.val);

                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            result.add(maxInLevel);
        }

        return result;
    }
}