描述
You need to find the largest value in each row of a binary tree.
Example:
1 2 3 4 5 6 7 8 9
| Input:
1 / \ 3 2 / \ \ 5 3 9
Output: [1, 3, 9]
|
分析
唔,这道题可能是用广度优先遍历的最佳示例?
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
class Solution { public List<Integer> largestValues(TreeNode root) { List<Integer> result = new LinkedList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int min = Integer.MIN_VALUE, size = queue.size(); while(!queue.isEmpty()) { min = Integer.MIN_VALUE; size = queue.size(); for (int i = 0; i < size; i++) { TreeNode nowNode = queue.poll(); min = Math.max(nowNode.val, min); if (nowNode.left != null) { queue.offer(nowNode.left); } if (nowNode.right != null) { queue.offer(nowNode.right); } } result.add(min); } return result; } }
|