python - 后序遍历此代码如何到达打印行 - Python

Question

我对后序遍历有疑问。

网上的代码是：

 def postorder(tree):
     if tree != None:
         postorder(tree.getLeftChild())
         postorder(tree.getRightChild())
         print(tree.getRootVal())

我不确定这将如何到达打印线。在这里它会一直向左走，直到没有左边，所以我们永远不会过去

 postorder(tree.getLeftChild())

当没有剩下这一行时：

 if tree != None:

不会满足，也不会打印。

Answer 1

考虑一片没有孩子的叶子。逐行：

 if tree != None:                      # isn't None, so continue
     postorder(tree.getLeftChild())    # will call postorder(None), which won't pass if
     postorder(tree.getRightChild())   # will call postorder(None), which won't pass if
     print(tree.getRootVal())          # will print

所以它会到达树的最底部，并在那里调用叶子的打印。然后它将递归备份。如您所述，左子树将在右子树之前打印。

特别是关于“永远不会过去”，它会的。让我们考虑这一行，再次为一片叶子：

postorder(tree.getLeftChild())

对于叶子getLeftChild返回无。所以这条线实际上意味着

postorder(None)

并且该if语句意味着该方法将什么都不做并且如果 None 被传递则返回。