后续遍历顺序是什么

在计算机科学中，后续遍历是二叉树遍历的一种方式。后续遍历意味着我们首先访问左子树，然后访问右子树，最后访问根节点。换句话说，如果访问节点的顺序是左，右，根，那么我们就是在执行后序遍历。

后续遍历是深度优先搜索树的一种方式，与前序遍历和中序遍历类似，是解决许多计算机科学问题的主要工具之一。通过深入分析后续遍历顺序，我们可以了解递归，动态编程，回溯和树遍历等多个方面的知识。

1. 后续遍历的特点

后续遍历的特点是在访问当前节点之前，我们需要先访问它的左子树和右子树。因此，在执行后续遍历之前，我们必须要遍历整个左子树和右子树。这种方式保证了节点被访问的顺序是从最底部开始，最后到达根节点。

2. 后续遍历的应用

后续遍历可以处理许多问题。其中一种常见的应用是计算二叉树的深度。在后续遍历中，我们首先计算左子树的深度，然后计算右子树的深度，最后返回深度更大的子树的深度加1。还有一种应用是构建表达式树。Postfix表达式树是通过后续遍历创建的。

3. 后续遍历的递归实现

下面是后续遍历的递归实现方法：

``` Python

def postorderTraversal(root):

"""

:type root: TreeNode

:rtype: List[int]

"""

if not root:

return []

stack, res = [root], []

while stack:

node = stack.pop()

res.append(node.val)

if node.left:

stack.append(node.left)

if node.right:

stack.append(node.right)

return res[::-1]

```

在这个例子中，我们使用了一个堆栈作为辅助空间，辅助节点的遍历顺序。我们首先将根节点推入堆栈中，然后进行迭代，直到堆栈为空。当我们弹出一个节点时，我们将其值添加到结果列表中，然后将其左右子节点添加到堆栈中。最后，我们将结果列表反转，以反顺序输出节点的值。

4. 后序遍历的时间复杂度和空间复杂度

对于递归方法，后序遍历的时间复杂度为O(n)，其中n是二叉树的节点数。这是因为我们遍历每个节点一次，且没有重复遍历任何节点。空间复杂度是O(h)，其中h是二叉树的高度。在最坏的情况下，二叉树是一条链，因此h=n。

另一方面，对于非递归方法，后序遍历的时间复杂度和空间复杂度也是O(n)和O(h)。这是因为节点最多只会被加入堆栈一次，除非左右子节点都还没有访问过。

总的来说，后序遍历是深度优先搜索树的一种方式。通过使用后序遍历，我们可以计算深度，构建表达式树等。同时，在了解后序遍历顺序及其实现方法的基础上，我们可以更好的理解递归，动态编程和回溯等多个方面的知识。