Given the root of a binary tree, return a list where each element is the largest value in its corresponding tree level.

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 is in the range [0, 10^4].
• -2^31 <= Node.val <= 2^31 - 1.

Method 1: Breadth-First Search with a Queue

We can perform a standard level-order traversal. For each level visited, we track the maximum value among the nodes at that level.

Implementation:

import java.util.*;

public class Solution {
    public List<Integer> largestLevelValues(TreeNode rootNode) {
        List<Integer> resultList = new ArrayList<>();
        if (rootNode == null) {
            return resultList;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(rootNode);
        
        while (!nodeQueue.isEmpty()) {
            int currentLevelSize = nodeQueue.size();
            int levelMax = Integer.MIN_VALUE;
            
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode currentNode = nodeQueue.poll();
                levelMax = Math.max(levelMax, currentNode.val);
                
                if (currentNode.left != null) {
                    nodeQueue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    nodeQueue.add(currentNode.right);
                }
            }
            resultList.add(levelMax);
        }
        return resultList;
    }
}

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes. Each node is processed once.
• Space Complexity: O(n) in the worst case for the queue storage.

Method 2: Depth-First Search (Recursive)

We can traverse the tree recursivley using a pre-order DFS approach. As we visit nodes, we keep track of the current depth and update a result list that stores the maximum value found for each depth.

Implementation:

import java.util.*;

public class Solution {
    public List<Integer> largestLevelValues(TreeNode rootNode) {
        List<Integer> maxValues = new ArrayList<>();
        findLevelMaximums(rootNode, 0, maxValues);
        return maxValues;
    }
    
    private void findLevelMaximums(TreeNode currentNode, int currentDepth, List<Integer> maxList) {
        if (currentNode == null) {
            return;
        }
        // If this is the first time we visit this depth, add the node's value.
        // Otherwise, update the value if the current node's value is larger.
        if (currentDepth == maxList.size()) {
            maxList.add(currentNode.val);
        } else {
            int existingMax = maxList.get(currentDepth);
            if (currentNode.val > existingMax) {
                maxList.set(currentDepth, currentNode.val);
            }
        }
        // Recurse for left and right children, incrementing the depth.
        findLevelMaximums(currentNode.left, currentDepth + 1, maxList);
        findLevelMaximums(currentNode.right, currentDepth + 1, maxList);
    }
}

Complexity Analysis:

• Time Complexity: O(n), as each node is visited once.
• Space Complexity: O(n) in the worst case due to the recursion call stack and the list for storing results.