postorder遍历此代码如何到达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语句意味着该方法将什么也不做，如果没有传递，则返回