首页二叉树前序遍历链表栈

二叉树前序遍历链表栈

时间: 2025-02-17 07:04:06 浏览: 33

### 使用栈实现二叉树前序遍历为了使用栈实现二叉树的前序遍历，可以遵循如下方法：在前序遍历中，访问顺序为“根-左-右”。当采用栈来模拟这一过程时，核心在于利用栈后进先出的特点。具体来说，在进入一个新的节点时，首先将其压入栈内；如果该节点存在，则记录其值（相当于访问），随后尝试转向它的左子节点继续上述操作。一旦遇到无左子节点的情况，便从栈顶弹出最近一次未探索右侧分支的节点，并转而考察这个节点的右子节点。下面是基于此逻辑编写的Python代码实例[^2]： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def preorderTraversal(root): if not root: return [] stack, output = [root], [] while stack: node = stack.pop() if node is not None: output.append(node.val) # 注意这里的顺序：因为栈是LIFO(last-in-first-out)，所以要先加右孩子再加左孩子 if node.right is not None: stack.append(node.right) if node.left is not None: stack.append(node.left) return output ``` 这段程序通过维护一个显式的`stack`用于存储待处理的节点指针以及一个`output`列表保存已访问过的节点值序列实现了非递归版本的前序遍历功能。每当取出一个新节点时就立即将它对应的数值添加到最终的结果集中去，接着依次把可能存在的两个子结点按特定次序推入堆栈等待后续处理直到整个数据结构被完全解析完毕为止。

阅读全文