两个问题,如何找到最后一层?如何找到最左端?
可以想到用BFS,一层一层向下迭代.
保持一个queue数组,循环时每次记录最左端的值,
直到queue中无元素,退出循环.
class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
queue = [root]
ans = 0
while any(queue):
// ans 一直为当前层最左端的元素的值
ans = queue[0].val
queue = [leaf for node in queue for leaf in (node.left,node.right) if leaf]
return ans
这里可以用高阶函数filter简化
def findLeftMostNode(self, root):
queue = [root]
for node in queue:
queue += filter(None, (node.right, node.left))
return node.val
如果filter参数值为None，就使用identity()函数，list参数中所有为假的元素都将被删除
