513 找树左下角的值（dfs、bfs）

一时失言乱红尘 2022-08-30 00:49 168阅读 0赞

**1. 问题描述：**

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

**示例 1:**

![20210717212211194.jpg][]

输入: root = \[2,1,3\]  
输出: 1

**示例 2:**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]**  
输入: \[1,2,3,4,null,5,6,null,null,7\]  
输出: 7

**提示:**  
二叉树的节点个数的范围是 \[1,10 ^ 4\]  
\-2 ^ 31 <= Node.val <= 2 ^ 31 - 1  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value

**2. 思路分析：**

分析题目可以知道我们可以使用**深搜**或者**宽搜**解决，使用宽搜则需要维护一个队列，队列中维护当前节点和当前节点深度的组合（python可以使用元组，c++可以使用结构体），宽搜先搜到的节点一定最左边的节点，我们可以维护当前节点的最大深度maxD，这样当当前节点的深度d更大的时候就更新最大深度maxD和答案res，这样当我们更新答案的时候就满足了两个条件：先搜到的节点并且深度是当前最大的。而使用深搜会更方便，只需要维护节点的深度即可，可以先搜左儿子，然后再搜右儿子，这样可以保证先搜到的节点一定是在最左边的节点，根据当前节点的深度决定是否更新当前的最大深度和答案，所以我们可以声明全局变量来记录当前遍历节点的最大深度maxD和答案res，如果深度更大那么就需要更新当前的最大深度和答案，这样更新的答案一定是当前深度最大并且是最左边的节点。深搜与宽搜的思路都是类似的，都需要维护最大深度maxD。

**3. 代码如下：**

**dfs:**

# class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        # maxD为最大深度
        maxD = 0
        res = 0
        # d用来记录当前遍历的节点的深度
        def dfs(self, root: TreeNode, d: int):
            if not root: return
            # 深度更大那么就需要更新最大深度maxD和答案res
            if d > self.maxD:
                self.maxD = d
                self.res = root.val
            self.dfs(root.left, d + 1)
            self.dfs(root.right, d + 1)
    
        def findBottomLeftValue(self, root: TreeNode) -> int:
            self.dfs(root, 1)
            return self.res

**bfs：**

import collections
    
    
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        def bfs(self, root: TreeNode):
            # python中的双端队列
            q = collections.deque()
            maxD = 1
            # 题目保证了至少一个节点
            res = root.val
            q.append((root, 1))
            while q:
                poll = q.pop()
                node, d = poll[0], poll[1]
                if d > maxD:
                    maxD = d
                    res = node.val
                # 注意是appendleft方法
                if node.left: q.appendleft((node.left, d + 1))
                if node.right: q.appendleft((node.right, d + 1))
            return res
    
        def findBottomLeftValue(self, root: TreeNode) -> int:
            return self.bfs(root)

[20210717212211194.jpg]: /images/20220829/d3aaa6550280421f8efbf4539b56cc0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/6a07f4283ab44509a5e411bf2fe3782d.png