### Python非递归算法实现二叉树的构建与后序遍历 以下是一个使用Python实现非递归算法构建二叉树并进行后序遍历输出的方法。此方法基于栈来模拟遍历过程，并结合了引用中的思路[^1]。 #### 1. 定义二叉树节点类 首先，定义一个`TreeNode`类，用于表示二叉树中的每个节点。 ```python class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None ``` #### 2. 非递归后序遍历实现 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。为了实现非递归版本，可以采用两个栈的方式[^2]。具体步骤如下： - 使用第一个栈存储遍历路径。 - 使用第二个栈存储最终结果的逆序输出。 以下是完整的代码实现： ```python def postorder_traversal(root): if not root: return [] stack1 = [] # 第一个栈用于遍历 stack2 = [] # 第二个栈用于存储逆序结果 result = [] # 最终结果列表 stack1.append(root) while stack1: node = stack1.pop() # 弹出当前节点 stack2.append(node) # 将该节点压入第二个栈 # 先将左子树压入第一个栈，再将右子树压入第一个栈 if node.left: stack1.append(node.left) if node.right: stack1.append(node.right) # 将第二个栈中的元素依次弹出，即为后序遍历的结果 while stack2: result.append(stack2.pop().val) return result ``` #### 3. 构建二叉树示例 以下是一个简单的二叉树构建示例： ```python # 构建二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) # 输出后序遍历结果 print(postorder_traversal(root)) # 输出: [4, 5, 2, 6, 7, 3, 1] ``` #### 4. 解释与优化 上述代码通过两个栈实现了非递归的后序遍历[^4]。虽然这种方法简单易懂，但也可以进一步优化为单栈实现。例如，通过标记访问状态或记录上一次访问的节点来减少额外的空间开销[^5]。 以下是单栈优化版本的代码： ```python def postorder_traversal_single_stack(root): if not root: return [] stack = [] result = [] cur = root pre = None while cur or stack: while cur: stack.append(cur) cur = cur.left top = stack[-1] if top.right and top.right != pre: # 如果右子树存在且未访问 cur = top.right else: # 否则访问当前节点 result.append(top.val) pre = stack.pop() return result ``` #### 示例输出 对于相同的二叉树结构，单栈优化版本的输出结果相同： ```python print(postorder_traversal_single_stack(root)) # 输出: [4, 5, 2, 6, 7, 3, 1] ``` --- ###