### 后序遍历定义
对于一棵任意的二叉树而言，在其后的顺序访问意味着按照“左子节点-右子节点-根节点”的顺序来依次访问每个节点。这样的遍历模式常用于需要先处理所有后代节点再返回到当前父节点的情况。
#### 1. **递归实现**
采用递归来实现后序遍历非常直观简洁：
python
def postorder_traversal_recursive(root):
if root is None:
return []
left_subtree = postorder_traversal_recursive(root.left)
right_subtree = postorderTraversal_recursive(root.right)
# 根据后序遍历规则将root结点放在最后
return left_subtree + right_subtree + [root.val]
上述代码首先检查给定的`root`是否为空；如果不空，则继续对其左右子树执行同样的后序遍历过程，然后合并得到的所有左侧、右侧子树的结果列表并将根节点值添加到最后形成最终结果。
#### 2. **非递归实现 (迭代法)**
相比于直接利用函数调用栈机制完成状态保存的递归方案，使用循环等非递归手段则需自行维护一个或多个辅助的数据结构以达到相同目的。以下是基于栈这一典型工具实现的一个示例：
python
from collections import deque
def postorder_traversal_iterative(root):
result = []
stack = deque([(True, root)])
while stack:
visit_left_first, node = stack.pop()
if not visit_left_first and node is not None:
result.append(node.val)
if node is not None:
# 先入栈右孩子，标记为不需要再次进入(visit=False)，然后再入栈左孩子并保持原始标志(visit=True)
if node.right is not None:
stack.append((False, node.right))
if visit_left_first or node.left is None:
continue
stack.append((True, node.left))
return result
在这个版本里，我们引入了一个布尔变量 `visit_left_first` 来决定接下来应该优先探索哪一侧的孩子节点。同时通过双端队列(stack)模拟了系统堆栈的行为，实现了无需显式递归也能完整地遵循"左子树->右子树->根节点"这个后序遍历规律的过程。
总结来说，无论是借助于自然形成的函数调用栈的递归策略还是手动构建临时存储空间进行逻辑控制的迭代方法，都能够有效地实现在不破坏原有二叉树结构的前提下对该树进行全面而有序的后序遍历。这两种不同的解决方案各自有着适用场景和特点，开发者可以根据实际需求灵活选择适合自己的实施方案。
标签： 二叉树的后序遍历算法
