513 找树左下角的值（dfs、bfs）-蒲公英云

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

1. 问题描述：

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

示例 1:

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

示例 2:

输入: [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)