算法题：在每个树行中找最大值
问题分析
解题思路
代码实现
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}
public class MaxValuesInEachRow {
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 levelSize = queue.size();
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
// 更新当前层的最大值
maxVal = Math.max(maxVal, currentNode.val);
// 将子节点加入队列
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
// 当前层遍历完了，记录最大值
result.add(maxVal);
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(3);
root.right = new TreeNode(2);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(9);
MaxValuesInEachRow solution = new MaxValuesInEachRow();
List<Integer> result = solution.largestValues(root);
System.out.println(result); // Output: [1, 3, 9]
}
}
代码解读
TreeNode 类，它代表二叉树的节点。然后，我们的 largestValues 方法实现了层次遍历的过程。我们用 queue来保存当前层的所有节点，每次从队列中取出一个节点，检查它的左右子节点，依次将它们加入队列。每次遍历一层，我们都记录该层的最大值，并将其添加到结果 result中。
Math.max() 来更新最大值。每层遍历结束后，将这个最大值存入 result。时间和空间复杂度分析
时间复杂度：O(N)，N 是树中的节点总数。每个节点只会被访问一次。 空间复杂度：O(W)，W 是树的最大宽度。在最坏的情况下，队列中会存储所有同一层的节点，空间复杂度是宽度的最大值。对于完全二叉树来说，最大宽度大约是 N/2。
代码的改进与优化
结语
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
