DSA 后序遍历

二叉树的后序遍历

后序遍历是一种深度优先搜索（Depth First Search），其中每个节点都以特定的顺序进行访问。 在此处 阅读更多关于二叉树遍历的信息。

对二叉树进行后序遍历的过程可视化如下

后序遍历通过递归地对左子树和右子树进行后序遍历，然后访问根节点来工作。 它用于删除树、表达式树的后缀表示法等。

之所以称这种遍历为“后”序，是因为访问节点是在递归调用左右子节点“之后”进行的。

后序遍历的代码看起来是这样的

def postOrderTraversal(node):
    if node is None:
        return
    postOrderTraversal(node.left)
    postOrderTraversal(node.right)
    print(node.data, end=", ")

postOrderTraversal() 函数将递归地继续遍历左子树（第 4 行），直到当 C 的左子节点作为 node 参数被调用时，返回 None。

在 C 的左子节点返回 None 之后，第 5 行执行，C 的右子节点返回 None，然后打印字母 'C'（第 6 行）。

这意味着 C 在其左子节点和右子节点被遍历“之后”才被访问或打印，这就是为什么它被称为“后”序遍历。

postOrderTraversal() 函数继续传播回先前的递归函数调用，因此下一个要打印的节点是 'D'，然后是 'A'。

该函数继续传播并打印节点，直到所有节点都被打印或访问。