参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

513.找树左下角的值

力扣题目链接

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

示例 1:

示例 2:

思路

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

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

递归

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

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

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

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

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

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

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

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

递归三部曲：

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

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

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

代码如下：

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

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

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

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

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

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

确定终止条件

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

代码如下：

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

确定单层递归的逻辑

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

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

完整代码如下：

class Solution {
public:
    int maxLen = INT_MIN;
    int maxleftValue;
    void traversal(TreeNode* root, int leftLen) {
        if (root->left == NULL && root->right == NULL) {
            if (leftLen > maxLen) {
                maxLen = leftLen;
                maxleftValue = root->val;
            }
            return;
        }
        if (root->left) {
            leftLen++;
            traversal(root->left, leftLen);
            leftLen--; // 回溯
        }
        if (root->right) {
            leftLen++;
            traversal(root->right, leftLen);
            leftLen--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return maxleftValue;
    }
};

当然回溯的地方可以精简，精简代码如下：

class Solution {
public:
    int maxLen = INT_MIN;
    int maxleftValue;
    void traversal(TreeNode* root, int leftLen) {
        if (root->left == NULL && root->right == NULL) {
            if (leftLen > maxLen) {
                maxLen = leftLen;
                maxleftValue = root->val;
            }
            return;
        }
        if (root->left) {
            traversal(root->left, leftLen + 1); // 隐藏着回溯
        }
        if (root->right) {
            traversal(root->right, leftLen + 1); // 隐藏着回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return maxleftValue;
    }
};

如果对回溯部分精简的代码不理解的话，可以看这篇257. 二叉树的所有路径

迭代法

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

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

如果对层序遍历不了解，看这篇二叉树：层序遍历登场！，这篇里也给出了层序遍历的模板，稍作修改就一过刷了这道题了。

代码如下：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // 记录最后一行第一个元素
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

总结

本题涉及如下几点：

递归求深度的写法，我们在110.平衡二叉树中详细的分析了深度应该怎么求，高度应该怎么求。
递归中其实隐藏了回溯，在257. 二叉树的所有路径中讲解了究竟哪里使用了回溯，哪里隐藏了回溯。
层次遍历，在二叉树：层序遍历登场！深度讲解了二叉树层次遍历。所以本题涉及到的点，我们之前都讲解过，这些知识点需要同学们灵活运用，这样就举一反三了。

其他语言版本

Java

// 递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

//迭代法
class Solution {

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == 0) {
                    res = poll.val;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}

Python

递归:

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        max_depth = -float("INF")
        leftmost_val = 0

        def __traverse(root, cur_depth): 
            nonlocal max_depth, leftmost_val
            if not root.left and not root.right: 
                if cur_depth > max_depth: 
                    max_depth = cur_depth
                    leftmost_val = root.val  
            if root.left: 
                cur_depth += 1
                __traverse(root.left, cur_depth)
                cur_depth -= 1
            if root.right: 
                cur_depth += 1
                __traverse(root.right, cur_depth)
                cur_depth -= 1

        __traverse(root, 0)
        return leftmost_val

迭代 - 层序遍历:

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        queue = deque()
        if root: 
            queue.append(root)
        result = 0
        while queue: 
            q_len = len(queue)
            for i in range(q_len): 
                if i == 0: 
                    result = queue[i].val 
                cur = queue.popleft()
                if cur.left: 
                    queue.append(cur.left)
                if cur.right: 
                    queue.append(cur.right)
        return result

Go

递归法：

 var maxDeep int // 全局变量 深度
 var  value  int //全局变量 最终值
func findBottomLeftValue(root *TreeNode) int {
     if root.Left==nil&&root.Right==nil{//需要提前判断一下（不要这个if的话提交结果会出错，但执行代码不会。防止这种情况出现，故先判断是否只有一个节点）
         return root.Val
     }
    findLeftValue (root,maxDeep)
    return value
}
func findLeftValue (root *TreeNode,deep int){
     //最左边的值在左边
     if root.Left==nil&&root.Right==nil{
         if deep>maxDeep{
             value=root.Val
             maxDeep=deep
         }
     }
    //递归
    if root.Left!=nil{
        deep++
        findLeftValue(root.Left,deep)
        deep--//回溯
    }
    if root.Right!=nil{
        deep++
        findLeftValue(root.Right,deep)
        deep--//回溯
    }
}

迭代法：

func findBottomLeftValue(root *TreeNode) int {
    queue:=list.New()
    var gradation int
    queue.PushBack(root)
    for queue.Len()>0{
        length:=queue.Len()
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*TreeNode)
            if i==0{gradation=node.Val}
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
        }
    }
    return gradation
}

JavaScript

递归版本：

var findBottomLeftValue = function(root) {
    //首先考虑递归遍历 前序遍历 找到最大深度的叶子节点即可
    let maxPath = 0,resNode = null;
    // 1. 确定递归函数的函数参数
    const dfsTree = function(node,curPath){
    // 2. 确定递归函数终止条件
        if(node.left===null&&node.right===null){
            if(curPath>maxPath){
            maxPath = curPath;
            resNode = node.val;
            }
            // return ;
        }
        node.left&&dfsTree(node.left,curPath+1);
        node.right&&dfsTree(node.right,curPath+1);
    }
    dfsTree(root,1);
    return resNode;
};

层序遍历：

var findBottomLeftValue = function(root) {
    //考虑层序遍历 记录最后一行的第一个节点
    let queue = [];
    if(root===null){
        return null;
    }
    queue.push(root);
    let resNode;
    while(queue.length){
        let length =  queue.length;
        for(let i=0; i<length; i++){
            let node = queue.shift();
            if(i===0){
                resNode = node.val;
            }
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return resNode;
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0513.找树左下角的值.md

0513.找树左下角的值.md

513.找树左下角的值

思路

递归

迭代法

总结

其他语言版本

Java

Python

Go

JavaScript

Files

0513.找树左下角的值.md

Latest commit

History

0513.找树左下角的值.md

File metadata and controls

513.找树左下角的值

思路

递归

迭代法

总结

其他语言版本

Java

Python

Go

JavaScript