当前位置：首页 > news >正文

【513. 找树左下角的值中等】

news 2025/6/23 9:48:54

题目：

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。

假设二叉树中至少有一个节点。

示例 1:
在这里插入图片描述
输入: root = [2,1,3]
输出: 1

示例 2:
在这里插入图片描述
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1

思路：

递归法

该题有一个容易迷惑的地方，就是最底层最左边的值并不一定是左叶子节点的值，比如输入：[1,null,1]，那最底层最左边的值就是右叶子节点的值：1。

所以递归的终止条件不能模仿 404. 左叶子之和中那样写，即不能写成下面这样：
```
if(node->left && !node->left->left && !node->left->right){    //  到达左叶子节点，将值累加到resultresult = node->left->val;
}
```
这样会漏掉左叶子节点为空，而右叶子节点有值的情况。

所以应该借助深度来写递归，即记录让深度值变大的第一个值，不论是左叶子节点，还是右叶子节点。最后一次记录的一定是最底层最左边的值。

递归三部曲：

确定递归函数的参数和返回值

参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。这里就不需要返回值了，所以递归函数的返回类型为void。

本题还需要类里的两个全局变量，maxLen用来记录最大深度，result记录最大深度最左节点的数值。

代码如下：
```
int maxDepth = INT_MIN;   // 全局变量 记录最大深度
int result;       // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* root, int depth)
```

确定终止条件

当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

代码如下：

if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {maxDepth = depth;           // 更新最大深度result = root->val;   // 最大深度最左面的数值
}
return;
}

确定单层递归的逻辑

在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：

	                // 中
if (root->left) {   // 左depth++; // 深度加一traversal(root->left, depth);depth--; // 回溯，深度减一
}
if (root->right) { // 右depth++; // 深度加一traversal(root->right, depth);depth--; // 回溯，深度减一
}
return;

迭代法

本题使用层序遍历再合适不过了，比递归要好理解得多！

只需要记录最后一行第一个节点的数值就可以了。

代码：

递归法

class Solution {
public:int maxDepth = INT_MIN; // 全局变量 记录最大深度int result; // 全局变量 最大深度最左节点的数值void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;    // 更新最大深度result = root->val; // 最大深度最左面的数值}return;}if (root->left) {depth++;traversal(root->left, depth);depth--; // 回溯}if (root->right) {depth++;traversal(root->right, depth);depth--; // 回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

迭代法

class Solution {
public:int findBottomLeftValue(TreeNode* root) {//  if(root == NULL) return 0;int result = 0;queue<TreeNode*> que1;if(root != NULL) que1.push(root);while(!que1.empty()){int size = que1.size();for(int i = 0; i < size; i++){TreeNode* node = que1.front();que1.pop();if(i == 0) result = node->val;  //  到达左叶子节点就替换result的值，最后一次就是最底层，最左边节点的值if(node->left) que1.push(node->left);if(node->right) que1.push(node->right);}}return result;}
};