Find Largest Value in Each Tree Row

• 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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<Integer> largestValues(TreeNode root) {18        List<Integer> result = new ArrayList<>();19        if (root == null) {20            return result;21        }22 23        Queue<TreeNode> queue = new LinkedList<>();24        queue.offer(root);25 26        while (!queue.isEmpty()) {27            int levelSize = queue.size();28            int maxInLevel = Integer.MIN_VALUE;29 30            for (int i = 0; i < levelSize; i++) {31                TreeNode currentNode = queue.poll();32                maxInLevel = Math.max(maxInLevel, currentNode.val);33 34                if (currentNode.left != null) {35                    queue.offer(currentNode.left);36                }37                if (currentNode.right != null) {38                    queue.offer(currentNode.right);39                }40            }41            result.add(maxInLevel);42        }43 44        return result;45    }46}

• Initialize an empty list result.
• Create a recursive helper function dfs(node, level, result).
• Start the process by calling dfs(root, 0, result).
• Inside the dfs function:
  • If the current node is null, return.
  • Check if the level is equal to the current size of the result list.
    • If yes, it's the first node at this level. Add node.val to result.
    • If no, a value for this level already exists. Update it with Math.max(result.get(level), node.val).
  • Recursively call dfs for the left child with level + 1.
  • Recursively call dfs for the right child with level + 1.
• Finally, return the result list.

A DFS approach can also solve this problem elegantly. We can use a pre-order traversal (Node -> Left -> Right) and maintain the current level of the traversal. We use a list, let's call it result, to store the largest value for each level. The index of the list corresponds to the level number.

We define a recursive helper function, dfs(node, level, result). When we visit a node at a given level, we check if this level is new. We can determine this by comparing the level with the current size of the result list. If level equals result.size(), it's the first time we've reached this depth, so we add the node's value to the result list. If level is less than result.size(), it means we've already visited a node at this level, so we simply update the existing maximum value at result.get(level) if the current node's value is greater. After processing the current node, we recursively call the function for its left and right children, incrementing the level by one.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<Integer> largestValues(TreeNode root) {18        List<Integer> result = new ArrayList<>();19        dfs(root, 0, result);20        return result;21    }22 23    private void dfs(TreeNode node, int level, List<Integer> result) {24        if (node == null) {25            return;26        }27 28        // If this is the first time we are visiting this level29        if (level == result.size()) {30            result.add(node.val);31        } else {32            // We have seen this level before, so update the max value33            result.set(level, Math.max(result.get(level), node.val));34        }35 36        // Recurse for children at the next level37        dfs(node.left, level + 1, result);38        dfs(node.right, level + 1, result);39    }40}