513.找树左下角的值

力扣题目链接(opens new window)

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

513.找树左下角的值

示例 2:

513.找树左下角的值1

思路

本地要找出树的最后一行找到最左边的值。此时大家应该想起用层序遍历是非常简单的了，反而用递归的话会比较难一点。

我们依然还是先介绍递归法。

递归

咋眼一看，这道题目用递归的话就就一直向左遍历，最后一个就是答案呗？

没有这么简单，一直向左遍历到最后一个，它未必是最后一行啊。

我们来分析一下题目：在树的最后一行找到最左边的值。

首先要是最后一行，然后是最左边的值。

如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。

如果对二叉树深度和高度还有点疑惑的话，请看：110.平衡二叉树 (opens new window)。

所以要找深度最大的叶子节点。

那么如果找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

递归三部曲：

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

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

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

代码如下：

1
2
3
int maxLen = INT_MIN;   // 全局变量 记录最大深度
int maxleftValue;       // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* root, int leftLen)

有的同学可能疑惑，为啥不能递归函数的返回值返回最长深度呢？

其实很多同学都对递归函数什么时候要有返回值，什么时候不能有返回值很迷茫。

如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！

初学者可能对这个结论不太理解，别急，后面我会安排一道题目专门讲递归函数的返回值问题。这里大家暂时先了解一下。

本题我们是要遍历整个树找到最深的叶子节点，需要遍历整棵树，所以递归函数没有返回值。

  1. 确定终止条件

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

代码如下：

1
2
3
4
5
6
7
if (root->left == NULL && root->right == NULL) {
    if (leftLen > maxLen) {
        maxLen = leftLen;           // 更新最大深度
        maxleftValue = root->val;   // 最大深度最左面的数值
    }
    return;
}
  1. 确定单层递归的逻辑

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

1
2
3
4
5
6
7
8
9
10
11
12
                    // 中
if (root->left) {   // 左
    leftLen++; // 深度加一
    traversal(root->left, leftLen);
    leftLen--; // 回溯，深度减一
}
if (root->right) { // 右
    leftLen++; // 深度加一
    traversal(root->right, leftLen);
    leftLen--; // 回溯，深度减一
}
return;

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	int deep = -1;
	int value = 0;
	public int findBottomLeftValue(TreeNode root) {
        if(root == null) return 0;
        findLeftValue(root,0);
        return value;
	}
	private void findLeftValue (TreeNode root,int left) {
        if(root.left == null && root.right == null) {
            if(left > deep) {
                value = root.val;
                deep = left;
            }
        }
        if(root.left != null) findLeftValue(root.left,left + 1);// 细节
        if(root.right != null) findLeftValue(root.right,left + 1);// 回溯
	}
}

跌代法就很简单 就是一个层序遍历 这里就不写了