Leetcode 513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
提示:
- 二叉树的节点个数的范围是
[1,10<sup>4</sup>] -2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1
解题思路：
要找到二叉树最后一行最左边的节点的值，可以使用广度优先搜索（BFS）的方法来解决。具体思路如下：
- 使用队列来进行广度优先搜索，首先将根节点入队。
- 在队列不为空的情况下，进行循环操作：
- 初始化一个变量
leftmost，用于记录当前层的最左边节点的值，默认为根节点的值。 - 获取当前层的节点数
size，用于控制内层循环的次数。 - 在内层循环中，依次从队列中取出
size个节点：- 如果当前节点有左子节点，将左子节点入队。
- 如果当前节点有右子节点，将右子节点入队。
- 更新
leftmost的值为当前节点的值。
- 内层循环结束后，
leftmost的值即为当前层的最左边节点的值。
- 初始化一个变量
- 返回
leftmost作为最终的答案。
还可以使用深度优先遍历：
- 定义一个变量
maxDepth，用于记录当前最大的深度值，初始值为0。 - 定义一个变量
leftmost，用于记录当前最左边节点的值。 - 编写辅助函数
dfs，该函数用于进行深度优先搜索。 - 在
dfs函数中，首先进行一个判断，如果当前节点为空，即到达了空节点，直接返回。 - 如果当前节点的深度大于
maxDepth，则更新maxDepth和leftmost的值为当前节点的值。 - 递归调用
dfs函数，依次处理左子树和右子树。 - 编写主函数
findBottomLeftValue，用于调用dfs函数并返回最终的结果。 - 在主函数中，首先进行一个判断，如果根节点为空，即整棵树为空树，直接返回0。
- 如果根节点不为空，那么调用
dfs函数，并返回leftmost作为最终的答案。
代码实现：
深度优先遍历：
class Solution {
int maxDepth = 0; // 当前最大的深度值
int leftmost = 0; // 当前最左边节点的值
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0; // 如果根节点为空，返回0
}
dfs(root, 1); // 调用深度优先搜索函数
return leftmost; // 返回最左边节点的值
}
private void dfs(TreeNode node, int depth) {
if (node == null) {
return; // 如果当前节点为空，直接返回
}
if (depth > maxDepth) {
maxDepth = depth; // 更新当前最大的深度值
leftmost = node.val; // 更新当前最左边节点的值
}
dfs(node.left, depth + 1); // 递归处理左子树
dfs(node.right, depth + 1); // 递归处理右子树
}
}
if (depth > maxDepth) {
maxDepth = depth;
leftmost = node.val;
}
Q:为什么这里可以确定node就是左子树的节点，而不是右子树的节点？
A:
在深度优先搜索的过程中，我们首先遍历左子树，然后再遍历右子树。因此，当我们访问到一个节点时，它的左子节点一定会先被访问到，然后才会访问右子节点。
在这段代码中，如果当前节点的深度 depth 大于当前最大深度 maxDepth，说明我们已经进入了下一层。因为我们是从根节点开始深度优先搜索的，所以当 depth 大于 maxDepth 时，当前节点一定是下一层的最左边节点。
因此，我们可以在这里更新 maxDepth 和 leftmost 的值，将当前节点的值赋给 leftmost。这样，当搜索完整棵树后，leftmost 就记录了最后一行最左边节点的值。
虽然在 dfs 函数中同时递归处理了左子树和右子树，但由于我们先访问左子树，所以在更新 maxDepth 和 leftmost 的时候，只有当 depth 大于 maxDepth 时，才会更新 leftmost 的值。这样确保了 leftmost 记录的是最后一行最左边的节点的值。
广度优先遍历：
class Solution {
public int findBottomLeftValue(TreeNode root) {
// 使用队列进行广度优先搜索
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点入队
// 初始化最左边节点的值为根节点的值
int leftmost = root.val;
while (!queue.isEmpty()) {
// 当前层的节点数
int size = queue.size();
// 当前层最左边节点的值
leftmost = queue.peek().val;
for (int i = 0; i < size; i++) {
// 取出当前节点
TreeNode node = queue.poll();
if (node.left != null) {
// 左子节点入队
queue.offer(node.left);
}
if (node.right != null) {
// 右子节点入队
queue.offer(node.right);
}
}
}
return leftmost; // 返回最左边节点的值
}
}
评论区