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

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

article 2025/1/5 6:55:05

题目：

给定一个二叉树的根节点 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){    //  到达左叶子节点，将值累加到result
	 result = 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;
    }
};