binary tree DC 模板
def dfs(node, size):
# if no such a node
if node is None:
# 目的一,default for empty tree
# 目的二,增广二叉树边缘的 None。【依此思考】
# if leaf
if node.left is None and node.right is None:
# 递归逻辑的真正出口
# 只有leaf的树的返回值。【依此思考】
# acquire answers
left_ans = dfs(node.left, size-1)
right...
# conbine answers
# return conbined answer
return Ans
return dfs(root) # dfs(root)[0]
要点
非递归的模板。非递归的DFS是用有限状态机来实现的。二叉树的话一共有4种状态。无论是pre/in/post-order,逻辑是完全一样的,只有顺序差别。 详情请看这个notebook
f(x)[0]
是只要第一个返回值的意思