513.找树左下角的值 Python DFS 、BFS双解！
一个优秀的内容风控解决方案应该是怎样的？
信息传播的媒介与形态五花八门，对于互联网平台来说，保障内容安全越来越难。当下互联网平台面临哪些困境？7月3日，腾讯安全思享会，带大家一起探索亟需的答案，限额报名
513.找树左下角的值
https://leetcode-cn.com/problems/find-bottom-left-tree-value/
难度：中等
题目：
给定一个二叉树，在树的*后一行找到*左边的值。
示例：
示例 1:
输入:
    2
   / \
  1   3
输出:
1
示例 2:
输入:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
输出:
7
分析
这虽然是一道中等题，但讲真的难度比较一般…
首先，*简单的应该是BFS逐层遍历
我们创建一个空列表，用于记录每行的*个val
然后创建一个队列，root入队，开始while循环
每行的*个节点入队，判断*个方式为比较index与列表的长度是否相等
知道队列为空时，终止循环，pop列表*后一个数值即可。
那么，这道题用DFS同样很简单
为了练习，这次我们使用一个字典保存
同样的递归遍历左子树和右子树
判断字典中是否包含该值，然后插入该值
由于是数字hash，所以其实是有序的，直接values.pop()即可。
解题-BFS：
from collections import deque
class Solution:
    def findBottomLeftValue(self, root):
        li, queue= [], deque([[root, 1]])
        while queue:
            for _ in range(len(queue)):
                child, index = queue.popleft()
                if len(li) < index:
                    li.append(child.val)
                index += 1
                if child.left:
                    queue.append([child.left, index])
                if child.right:
                    queue.append([child.right, index])
        return li.pop()
解题-DFS:
class Solution:
    def findBottomLeftValue(self, root):
        d = {}
        def dfs(child, index):
            if not child:
                return
            if index not in d:
                d[index] = child.val
            dfs(child.left, index + 1)
            dfs(child.right, index + 1)
        dfs(root, 1)
        return list(d.values()).pop()