DSA 后序遍历

二叉树的后序遍历

后序遍历是一种深度优先搜索，其中每个节点以特定顺序访问。 阅读有关二叉树遍历的更多信息 这里.

对二叉树进行后序遍历可以这样可视化

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

使这种遍历成为“后序”的原因是，访问节点是在递归地调用左子节点和右子节点“之后”完成的。

这是后序遍历代码的样子

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'。

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