pylist

Binary Tree

模板和要点

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

Examples

MISC