从 寻找最底层最左边的结点 复习DFS 和 BFS 在二叉树中的运用。以下是自己瞎写的版本。
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def dfs(self, root: TreeNode) -> list[int]:
if not root.left and not root.right:
return [root.val, 0] # [val, level]
elif not root.left:
ans = dfs(self, root.right)
return [ans[0], ans[1] + 1]
elif not root.right:
ans = dfs(self, root.left)
return [ans[0], ans[1] + 1]
else:
ans_left, ans_right = dfs(self, root.left), dfs(self, root.right)
if ans_left[1] >= ans_right[1]:
ans = ans_left
else:
ans = ans_right
return [ans[0], ans[1] + 1]
return dfs(self, root)[0]
自己写的DFS虽然很容易理解，但有多次重复的分类。完全可以在首行对node进行判定是否为None，以缩减整体DFS的篇幅。一开始这么写也是理解错了题意，以为是要写最底层的左结点，所以做出了一点变化。
以下给出标答的DFS和BFS
# DFS
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
curVal = curHeight = 0
def dfs(node: Optional[TreeNode], height: int) -> None:
if node is None:
return
height += 1
dfs(node.left, height)
dfs(node.right, height)
nonlocal curVal, curHeight
if height > curHeight:
curHeight = height
curVal = node.val
dfs(root, 0)
return curVal
# BFS
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
q = deque([root])
while q:
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
ans = node.val
return ans
'''
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/find-bottom-left-tree-value/solution/zhao-shu-zuo-xia-jiao-de-zhi-by-leetcode-weeh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
'''
DFS很清晰明了，主要学习BFS的写法。这里引用了 deque 模块，隶属于 collections 。本质上类似于列表，但两边都可以进出，有快捷添加和删除的方法。
from collections import deque
d = deque([5])
# append
d.append(10)
d.append(15)
# pop
d.pop()
d.leftpop()
# maxlen
d=deque(maxlen=20)
for i in range(30):
d.append(str(i))
# 此时d的值为d=deque(['10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29'], maxlen=20)
# 可见当限制长度的deque增加超过限制数的项时，另一边的项会自动删除。
# extend
d=deque([1,2,3,4,5])
d.extend([0])
# 那么此时d=deque([1,2,3,4,5,0])
d.extendleft([6,7,8])
# 此时d=deque([8, 7, 6, 1, 2, 3, 4, 5, 0])