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()
