前序中序后序遍历区别：对比表格与记忆口诀

对比表格：

| 遍历方式 | 访问顺序 | 举例 |

| | | |

| 前序遍历 | 根节点 -> 左子树 -> 右子树 | 先访问根节点，然后访问左子树，最后访问右子树 |

| 中序遍历 | 左子树 -> 根节点 -> 右子树 | 先访问左子树，然后访问根节点，最后访问右子树 |

| 后序遍历 | 左子树 -> 右子树 -> 根节点 | 先访问左子树，然后访问右子树，最后访问根节点 |

记忆口诀：

1. 前序遍历：首先老大（根节点）出来，然后老二（左子树）和老三（右子树）跟着。

2. 中序遍历：先让老二（左子树）出来，然后老大（根节点）出来，最后老三（右子树）出来。

3. 后序遍历：先让老二（左子树）和老三（右子树）出来，最后老大（根节点）出来。

这三种遍历方式在二叉树的算法中非常常见，它们被广泛应用于搜索、插入、删除等操作。在编程中，我们通常会使用递归或迭代的方式来实现这三种遍历。

递归实现：

python

前序遍历

def preorder_traversal(root):

if root:

print(root.val) 访问根节点

preorder_traversal(root.left) 递归遍历左子树

preorder_traversal(root.right) 递归遍历右子树

中序遍历

def inorder_traversal(root):

if root:

inorder_traversal(root.left) 递归遍历左子树

print(root.val) 访问根节点

inorder_traversal(root.right) 递归遍历右子树

后序遍历

def postorder_traversal(root):

if root:

postorder_traversal(root.left) 递归遍历左子树

postorder_traversal(root.right) 递归遍历右子树

print(root.val) 访问根节点

迭代实现（使用栈）：

python

前序遍历

def preorder_traversal_iterative(root):

if not root:

return

stack, node = [root], root

while stack or node:

while node:

print(node.val) 访问根节点

stack.append(node)

node = node.left

node = stack.pop()

if node.right:

node = node.right

中序遍历

def inorder_traversal_iterative(root):

if not root:

return

stack = []

while root or stack:

while root:

stack.append(root)

root = root.left

node = stack.pop()

print(node.val) 访问根节点

root = node.right

后序遍历

def postorder_traversal_iterative(root):

if not root:

return

stack, output = [], []

node = root

while node or stack:

while node:

stack.append(node)

node = node.left

node = stack.pop()

output.append(node.val) 先将节点值放入输出列表

if node.right:

node = node.right

else:

node = None

return output[::-1] 反转输出列表，得到后序遍历结果