<p>以下是对先前答案的补充。我在您的原始代码中添加了一些打印输出,以便逐步演示递归的工作原理</p>
<pre><code>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)))
</code></pre>
<pre><code>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
</code></pre>