二叉树前序、中序、后序的非递归（迭代）的统一化模板实现（python）（csdn）————程序.pdf

二叉树的遍历是数据结构与算法中的基础概念，尤其在面试中经常被考察。本文主要讨论了二叉树的前序、中序、后序遍历的非递归（迭代）实现，并提供了一个统一的模板。在了解非递归实现之前，我们先回顾一下递归实现的思路。 递归实现非常直观，三种遍历的递归代码几乎相同，只是访问子节点的顺序稍有不同。例如，后序遍历的Python代码如下： ```python class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: res = list() def postorder(root): if not root: return postorder(root.left) postorder(root.right) res.append(root.val) postorder(root) return res ``` 只需调整子节点的访问顺序，即可得到前序或中序遍历。对于前序遍历，顺序为根左右；对于中序遍历，顺序为左根右。 然而，面试官通常会要求使用非递归（迭代）的方法来实现这些遍历。非递归实现通常使用栈来模拟递归过程。以下是后序遍历的非递归迭代实现： ```python class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [(False, root)] while stack: visit, node = stack.pop() if not node: continue if not visit: stack.append((True, node)) stack.append((False, node.right)) stack.append((False, node.left)) else: res.append(node.val) return res ``` 这个模板的关键在于使用一个元组 `(visit, node)` 存储节点，其中 `visit` 表示节点是否已访问。在栈中，我们首先处理未访问的节点，然后按照右子节点、左子节点的顺序将其压入栈。当访问一个节点时，我们将其标记为已访问并将其值添加到结果列表中。 通过调整入栈顺序，我们可以实现前序和中序遍历。对于前序遍历，入栈顺序应为根左右，即： ```python stack.append((True, node)) stack.append((False, node.left)) stack.append((False, node.right)) ``` 而对于中序遍历，入栈顺序为左根右： ```python stack.append((False, node.left)) stack.append((True, node)) stack.append((False, node.right)) ``` 这个通用模板的优点在于，它简化了不同遍历方式的实现，将较简单的前序和中序遍历与较复杂的后序遍历统一在一个框架下。注意，由于栈遵循后进先出（LIFO）原则，所以入栈的顺序与实际遍历顺序是相反的。例如，后序遍历的顺序是左右根，但在栈中则需要按照根右左的顺序操作。 总结来说，二叉树的前序、中序、后序遍历的非递归迭代实现可以通过调整一个通用模板中的关键部分来完成。这种实现方式不仅避免了递归带来的栈溢出问题，还提高了代码的复用性和可读性。在面试或实际编程中，掌握这种非递归遍历方法对解决相关问题至关重要。