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:
[0, 104].-231 <= Node.val <= 231 - 1The BFS approach involves traversing the tree level by level and keeping track of the largest value at each level. We employ a queue data structure to facilitate level-wise traversal and maintain a list to store the maximum values for each row.
This solution uses a queue to perform a BFS traversal on the binary tree. Each level is processed entirely before moving to the next, and the largest value encountered at each level is recorded in the result array. The function returns the array of largest values and updates the size of the returned array via the pointer returnSize.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of nodes in the tree, since each node is processed exactly once. Space Complexity: O(n) due to the storage required to keep the queue and the result array.
The DFS approach involves recursively exploring each branch of the tree depth-first and leveraging the depth of recursion to determine the level of the tree. For each level not yet considered, the maximum value is initialized, or updated if a new larger value is found.
This C++ solution employs a depth-first search (DFS) paradigm using recursion. We track the depth to associate the maximum value found at each level. If a given depth isn’t present in the list of maximum values, it initializes it; otherwise, it updates the level’s maximum with the current node’s value if it exceeds the current maximum.
Java
Python
Time Complexity: O(n) where n is the number of nodes in the tree, since every node is visited once. Space Complexity: O(h) where h is the height of the tree due to recursion stack.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n) where n is the number of nodes in the tree, since each node is processed exactly once. Space Complexity: O(n) due to the storage required to keep the queue and the result array. |
| Depth-First Search (DFS) Approach | Time Complexity: O(n) where n is the number of nodes in the tree, since every node is visited once. Space Complexity: O(h) where h is the height of the tree due to recursion stack. |
LeetCode Find Largest Value In Each Tree Row Explained - Java • Nick White • 17,048 views views
Watch 9 more video solutions →Practice Find Largest Value in Each Tree Row with our built-in code editor and test cases.
Practice on FleetCode