LeetCode 515: Find Largest Value in Each Tree Row
Problem Description
Explanation
To solve this problem, we can perform a level-order traversal of the binary tree and at each level, find the maximum value. We can use a queue data structure to keep track of nodes at each level. We will traverse each level and find the maximum value for that level.
- Initialize a queue with the root node.
- While the queue is not empty, iterate over the nodes at the current level.
- For each node, update the maximum value for that level.
- Add the child nodes to the queue for the next level.
- Repeat the process until all levels are traversed.
The time complexity of this approach is O(N), where N is the number of nodes in the tree. The space complexity is also O(N) in the worst case.
Solutions
import java.util.*;
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 size = queue.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
max = Math.max(max, node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(max);
}
return result;
}
}Related LeetCode Problems
Loading editor...