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

513.找树左下角的值

力扣题目链接

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

示例 1:

示例 2:

算法公开课

《代码随想录》算法视频公开课：怎么找二叉树的左下角？递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路

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

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

递归

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

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

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

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

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

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

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

那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

递归三部曲：

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

参数必须有要遍历的树的根节点，还有就是一个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 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) {
            traversal(root->left, depth + 1); // 隐藏着回溯
        }
        if (root->right) {
            traversal(root->right, depth + 1); // 隐藏着回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

如果对回溯部分精简的代码不理解的话，可以看这篇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:
        self.max_depth = float('-inf')
        self.result = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if node.left:
            depth += 1
            self.traversal(node.left, depth)
            depth -= 1
        if node.right:
            depth += 1
            self.traversal(node.right, depth)
            depth -= 1

（版本二）递归法+精简

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = float('-inf')
        self.result = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if node.left:
            self.traversal(node.left, depth+1)
        if node.right:
            self.traversal(node.right, depth+1)

(版本三）迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def findBottomLeftValue(self, root):
        if root is None:
            return 0
        queue = deque()
        queue.append(root)
        result = 0
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == 0:
                    result = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

Go

递归法：

var depth int   // 全局变量 最大深度
var res int     // 记录最终结果
func findBottomLeftValue(root *TreeNode) int {
    depth, res = 0, 0   // 初始化
    dfs(root, 1)
    return res
}

func dfs(root *TreeNode, d int) {
    if root == nil {
        return
    }
    // 因为先遍历左边，所以左边如果有值，右边的同层不会更新结果
    if root.Left == nil && root.Right == nil && depth < d { 
        depth = d
        res = root.Val
    }
    dfs(root.Left, d+1)   // 隐藏回溯
    dfs(root.Right, d+1)
}

迭代法：

func findBottomLeftValue(root *TreeNode) int {
    var gradation int
    queue := list.New()
    
    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;
            }
        }
        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;
};

TypeScript

递归法：

function findBottomLeftValue(root: TreeNode | null): number {
    function recur(root: TreeNode, depth: number): void {
        if (root.left === null && root.right === null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                resVal = root.val;
            }
            return;
        }
        if (root.left !== null) recur(root.left, depth + 1);
        if (root.right !== null) recur(root.right, depth + 1);
    }
    let maxDepth: number = 0;
    let resVal: number = 0;
    if (root === null) return resVal;
    recur(root, 1);
    return resVal;
};

迭代法：

function findBottomLeftValue(root: TreeNode | null): number {
    let helperQueue: TreeNode[] = [];
    if (root !== null) helperQueue.push(root);
    let resVal: number = 0;
    let tempNode: TreeNode;
    while (helperQueue.length > 0) {
        resVal = helperQueue[0].val;
        for (let i = 0, length = helperQueue.length; i < length; i++) {
            tempNode = helperQueue.shift()!;
            if (tempNode.left !== null) helperQueue.push(tempNode.left);
            if (tempNode.right !== null) helperQueue.push(tempNode.right);
        }
    }
    return resVal;
};

Swift

递归版本：

var maxLen = -1
var maxLeftValue = 0
func findBottomLeftValue_2(_ root: TreeNode?) -> Int {
    traversal(root, 0)
    return maxLeftValue
}

func traversal(_ root: TreeNode?, _ deep: Int) {
    guard let root = root else {
        return
    }

    if root.left == nil && root.right == nil {
        if deep > maxLen {
            maxLen = deep
            maxLeftValue = root.val
        }
        return
    }
    
    if root.left != nil {
        traversal(root.left, deep + 1)
    }
    
    if root.right != nil {
        traversal(root.right, deep + 1)
    }
    return
}

层序遍历：

func findBottomLeftValue(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    
    var queue = [root]
    var result = 0
    
    while !queue.isEmpty {
        let size = queue.count
        for i in 0..<size {
            let firstNode = queue.removeFirst()
          
            if i == 0 {
                result = firstNode.val
            }
            
            if let leftNode = firstNode.left {
                queue.append(leftNode)
            }
            
            if let rightNode = firstNode.right {
                queue.append(rightNode)
            }
        }
    }
    return result
}

Scala

递归版本:

object Solution {
  def findBottomLeftValue(root: TreeNode): Int = {
    var maxLeftValue = 0
    var maxLen = Int.MinValue
    // 递归方法
    def traversal(node: TreeNode, depth: Int): Unit = {
      // 如果左右都为空并且当前深度大于最大深度，记录最左节点的值
      if (node.left == null && node.right == null && depth > maxLen) {
        maxLen = depth
        maxLeftValue = node.value
      }
      if (node.left != null) traversal(node.left, depth + 1)
      if (node.right != null) traversal(node.right, depth + 1)
    }
    traversal(root, 0)  // 调用方法
    maxLeftValue    // return关键字可以省略
  }
}

层序遍历:

  import scala.collection.mutable

  def findBottomLeftValue(root: TreeNode): Int = {
    val queue = mutable.Queue[TreeNode]()
    queue.enqueue(root)
    var res = 0   // 记录每层最左侧结果
    while (!queue.isEmpty) {
      val len = queue.size
      for (i <- 0 until len) {
        val curNode = queue.dequeue()
        if (i == 0) res = curNode.value // 记录最最左侧的节点
        if (curNode.left != null) queue.enqueue(curNode.left)
        if (curNode.right != null) queue.enqueue(curNode.right)
      }
    }
    res // 最终返回结果，return关键字可以省略
  }

Rust

层序遍历

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut queue = VecDeque::new();
        let mut res = 0;
        if root.is_some() {
            queue.push_back(root);
        }
        while !queue.is_empty() {
            for i in 0..queue.len() {
                let node = queue.pop_front().unwrap().unwrap();
                if i == 0 {
                    res = node.borrow().val;
                }
                if node.borrow().left.is_some() {
                    queue.push_back(node.borrow().left.clone());
                }
                if node.borrow().right.is_some() {
                    queue.push_back(node.borrow().right.clone());
                }
            }
        }
        res
    }
}

递归

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    //*递归*/
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = 0;
        let mut max_depth = i32::MIN;
        Self::traversal(root, 0, &mut max_depth, &mut res);
        res
    }
    fn traversal(
        root: Option<Rc<RefCell<TreeNode>>>,
        depth: i32,
        max_depth: &mut i32,
        res: &mut i32,
    ) {
        let node = root.unwrap();
        if node.borrow().left.is_none() && node.borrow().right.is_none() {
            if depth > *max_depth {
                *max_depth = depth;
                *res = node.borrow().val;
            }
            return;
        }
        if node.borrow().left.is_some() {
            Self::traversal(node.borrow().left.clone(), depth + 1, max_depth, res);
        }
        if node.borrow().right.is_some() {
            Self::traversal(node.borrow().right.clone(), depth + 1, max_depth, res);
        }
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0513.找树左下角的值.md

0513.找树左下角的值.md

513.找树左下角的值

算法公开课

思路

递归

迭代法

总结

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Swift

Scala

Rust

Files

0513.找树左下角的值.md

Latest commit

History

0513.找树左下角的值.md

File metadata and controls

513.找树左下角的值

算法公开课

思路

递归

迭代法

总结

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Swift

Scala

Rust