二叉树后序遍历怎么看

二叉树是数据结构中最常用的树形结构之一，其中后序遍历是一种遍历二叉树的方式。开始学习二叉树后序遍历时，很多人会感到困惑，不知道从哪里入手，如何加深印象，下面我们将从多个角度出发，为大家详细讲解如何看懂二叉树后序遍历。

1. 概述

首先，让我们先来了解一下什么是二叉树后序遍历。二叉树后序遍历是指先遍历左子树，再遍历右子树，最后访问根节点的一种遍历方式。具体来说，假设我们有一颗如下所示的二叉树：

```

1

/ \

2 3

/ \

4 5

```

那么它的后序遍历顺序就是：4 5 2 3 1。首先遍历左子树，得到4 5，接着遍历右子树2 3，最后访问根节点1。

2. 递归

经过上面的了解，我们知道后序遍历的遍历顺序，但是具体如何进行遍历呢？这里我们介绍一种最常用的方式，那就是递归。具体来说，我们可以使用如下的伪代码：

```

def post_order_traversal(self, root):

if root is None:

return None

self.post_order_traversal(root.left)

self.post_order_traversal(root.right)

print(root.val)

```

这段代码使用了递归的方式遍历二叉树，先遍历左子树，再遍历右子树，最后访问根节点。值得注意的是，在每次遍历左子树和右子树之后，我们都会访问该节点，这也是后序遍历的特征。

3. 非递归

除了递归之外，我们还可以使用非递归的方式实现后序遍历。具体来说，可以使用栈来存储遍历的路径，从而实现非递归的后序遍历。我们可以使用如下的伪代码：

```

def post_order_traversal(self, root):

if root is None:

return None

stack = []

prev = None

while stack or root:

while root:

stack.append(root)

root = root.left

root = stack.pop()

if root.right is None or root.right == prev:

print(root.val)

prev = root

root = None

else:

stack.append(root)

root = root.right

```

这段代码使用了栈来存储节点，我们先将左子树的所有节点存入栈中，接着在遍历右子树之前，判断该节点的右子树是否被访问过，如果没有，将其右节点存入栈中继续遍历。如果访问完右子树或者右子树已被访问，就访问该节点。

4. 应用

那么后序遍历有什么应用呢？其实，在很多实际问题中，都可以使用后序遍历来解决。例如，在算法设计中，逆波兰表达式求值就需要用到后序遍历，而在图形学中，后序遍历可以用来绘制三维物体，实现透明效果，等等。

综上所述，二叉树后序遍历是遍历二叉树的一种方式，其具体实现包括递归和非递归。通过后序遍历，我们可以解决很多实际问题，实现各种算法和应用。希望本文能为大家提供一些帮助，更好地理解和掌握二叉树后序遍历。