为什么在这里调用函数MaxDepth会返回深度？

Question

class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Compute the "maxDepth" of a tree -- the number of nodes
# along the longest path from the root node down to the
# farthest leaf node
def maxDepth(node):
    if node is None:
        return 0 ;
 
    else :
 
        # Compute the depth of each subtree
        lDepth = maxDepth(node.left)   #HERE <--------------------
        rDepth = maxDepth(node.right)
 
        # Use the larger one
        if (lDepth > rDepth):
            return lDepth+1
        else:
            return rDepth+1
 
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
 
print ("Height of tree is %d" %(maxDepth(root)))

所有这一切都是递归地进入maxDepth，直到不再有node.left或node.right，这如何返回深度

我已经在这里发表了评论来说明我困惑的地方。此代码如何知道要分配lDepth和rDepth的值

Answer 1

您可以这样想函数：

每一棵树都可以递归地被认为是一棵树，它的左右两侧各有两个子树。 因此，每个树的最大深度递归定义为左、右子树深度的最大值加上一

对于这种递归，可以选择两种等价的基本情况：

1. None节点的深度为0
2. 没有子节点（叶）的节点的深度为1

在本例中，您选择了第一个基本情况

以下图为例：

    A    < - maxDepth(A) = max(maxDepth(B), maxDepth(C)) + 1
   / \
  B   C  < - maxDepth(C) = 1, maxDepth(B) = max(maxDepth(D), maxDepth(E)) + 1
 / \
D   E   <   maxDepth(D) = 1, maxDepth(E) = maxDepth(F) + 1
   /
  F     <   maxDepth(F) = 1

Answer 2

以下是对先前答案的补充。我在您的原始代码中添加了一些打印输出，以便逐步演示递归的工作原理

class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


# Compute the "maxDepth" of a tree   the number of nodes
# along the longest path from the root node down to the
# farthest leaf node
def maxDepth(node):
    if node:
        print(f"Current node: {node.data}")
    if node is None:
        print("Current node: None")
        return 0

    else:

        # Compute the depth of each subtree
        lDepth = maxDepth(node.left)  # HERE <          
        print("lDepth traversal finished")
        rDepth = maxDepth(node.right)
        print("rDepth traversal finished")

        # Use the larger one
        if (lDepth > rDepth):
            print(f"lDepth: {lDepth} | rDepth: {rDepth}, return lDepth+1")
            return lDepth + 1
        else:
            print(f"lDepth: {lDepth} | rDepth: {rDepth}, return rDepth+1")
            return rDepth + 1


# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Height of tree is %d" % (maxDepth(root)))

Current node: 1                           < - caller: last line
Current node: 2                           < - caller: lDepth = maxDepth(node.left) on tree lvl1 (node(1))
Current node: 4                           < - caller: lDepth = maxDepth(node.left) on tree lvl2 (node(2))
Current node: None                        < - caller: lDepth = maxDepth(node.left) on tree lvl3 (node(4))
lDepth traversal finished                 < - back to tree lvl3 (node(4))
Current node: None                        < - caller: rDepth = maxDepth(node.right) on tree lvl3 (node(4))
rDepth traversal finished                 < - back to tree lvl3 (node(4))
lDepth: 0 | rDepth: 0, return rDepth+1
lDepth traversal finished                 < - back to tree lvl2 (node(2))
Current node: 5                           < - caller: rDepth = maxDepth(node.right) on tree lvl2 (node(2))
Current node: None                        < - caller: lDepth = maxDepth(node.left) on tree lvl3 (node(5))
lDepth traversal finished                 < - back to tree lvl3 (node(5))
Current node: None                        < - caller: rDepth = maxDepth(node.right) on tree lvl3 (node(5))
rDepth traversal finished                 < - back to tree lvl3 (node(5))
lDepth: 0 | rDepth: 0, return rDepth+1
rDepth traversal finished                 < - back to tree lvl2 (node(2))
lDepth: 1 | rDepth: 1, return rDepth+1
lDepth traversal finished                 < - back to tree lvl1 (node(1))
Current node: 3                           < - caller: rDepth = maxDepth(node.right) on tree lvl1 (node(1))
Current node: None                        < - caller: lDepth = maxDepth(node.left) on tree lvl2 (node(3))
lDepth traversal finished                 < - back to tree lvl2 (node(3))
Current node: None                        < - caller: rDepth = maxDepth(node.right) on tree lvl2 (node(3))
rDepth traversal finished                 < - back to tree lvl2 (node(3))
lDepth: 0 | rDepth: 0, return rDepth+1
rDepth traversal finished                 < - back to tree lvl1 (node(1))
lDepth: 2 | rDepth: 1, return lDepth+1    < - finish recursion
Height of tree is 3