节点上的Max()函数；蟒蛇DFS

Question

在下面的DFS经典例子中：

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def tree_max_depth(root: Node) -> int:
    def dfs(root):
        # null node adds no depth
        if not root:
            return 0
        # num nodes in longest path of current subtree = max num nodes of its two subtrees + 1 current node
        return max(dfs(root.left), dfs(root.right)) + 1
    print(dfs(root.left))
    return dfs(root) - 1 if root else 0

# this function builds a tree from input; you don't have to modify it
# learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
def build_tree(nodes, f):
    val = next(nodes)
    if val == 'x': return None
    left = build_tree(nodes, f)
    right = build_tree(nodes, f)
    return Node(f(val), left, right)

if __name__ == '__main__':
    root = build_tree(iter(input().split()), int)
    res = tree_max_depth(root)
    print(res)

max 函数如何计算下面这一行的高度？

return max(dfs(root.left), dfs(root.right)) + 1

Answer 1

如果你理解递归，那么你就能理解代码块的作用。

假设初始节点是A。一开始，

max(dfs(root.left), dfs(root.right)) + 1

就像在说

max(dfs(nodeB), dfs(nodeC)) + 1

。

• 首先，它计算

  dfs(nodeB)

  。这不是根，所以它不会返回 0。

• 继续

  max(dfs(nodeD), dfs(nodeE)) + 1

  。

• 它转到 NodeD (root.left)，即 root，因此它返回 0+1=1。

• 然后，继续到

  dfs(nodeE)

  （root.right）。它不是 root，所以它转到 dfs(nodeF)。 dfs(nodeF) 是根，因此返回 0+1。

现在，我们对于 B 节点，代码

max(1, 2)

，其中“1”来自 root.left（nodeD），“2”来自节点 E 和 F。选择最大值，即 2，然后将 2+1 返回到节点 A。

节点 C，高度为 1。因此，

max(3,1)

为 1。因此，最大高度为 3。