在Java中，堆栈存储二叉树主要用于非递归遍历（如先序、中序、后序），通过堆栈的LIFO特性暂存节点：根节点先入栈，循环中弹出节点处理，再按特定顺序压入子节点（如先序需先右后左），从而模拟递归调用栈实现深度优先遍历。
在Java中，堆栈（Stack）通过非递归的深度优先遍历（DFS）存储二叉树数据，核心思路是利用栈的LIFO（后进先出）特性模拟递归过程,以下是详细实现方法及原理：
堆栈存储二叉树的底层逻辑
堆栈本身不直接“存储”二叉树结构，而是通过辅助遍历将节点按特定顺序存入栈中,实现以下操作：
- 替代递归：避免递归导致的栈溢出（StackOverflowError）
- 控制访问顺序：按前序/中序/后序遍历节点
- 空间效率：空间复杂度O(h)（h为树高），优于递归的O(n)
堆栈遍历二叉树的三种方式（附Java代码）
前序遍历（根→左→右）
public void preOrderStack(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " "); // 访问根节点
// 右子节点先入栈（保证左子节点先出栈）
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
执行流程：
- 根节点入栈 → 弹出并访问
- 右子节点入栈 → 左子节点入栈
- 重复弹出栈顶节点（左子优先）
中序遍历（左→根→右）
public void inOrderStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 深入左子树到底部
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
System.out.print(curr.val + " "); // 访问节点
curr = curr.right; // 转向右子树
}
}
执行流程：
- 从根节点向左深入，所有左子节点入栈
- 弹出栈顶（最左节点）并访问
- 处理该节点的右子树
后序遍历（左→右→根）
public void postOrderStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> result = new Stack<>(); // 辅助栈存储结果
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.push(node.val); // 根节点值存入结果栈
// 左子节点先入栈（保证右子节点先进入结果栈）
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
// 反向输出结果栈（实现左右根→根右左的逆序）
while (!result.isEmpty()) {
System.out.print(result.pop() + " ");
}
}
关键点：
利用辅助栈反转访问顺序（根→右→左 → 逆序输出为左→右→根）
堆栈 vs 递归的对比
| 特性 | 堆栈实现 | 递归实现 |
|---|---|---|
| 空间复杂度 | O(h) (h=树高度) | O(n) (递归深度) |
| 栈溢出风险 | 无 | 树过高时可能发生 |
| 代码可控性 | 高（显式控制栈操作） | 低（依赖系统调用栈） |
| 适用场景 | 超深二叉树、迭代逻辑 | 代码简洁性要求高 |
应用场景
- 深度优先搜索（DFS）：路径查找、回溯算法
- 表达式树求值：通过后序遍历栈计算
- 序列化二叉树：前序+中序遍历栈重建二叉树
- 非递归算法优化：避免递归层级限制（如Java默认栈深度~10,000）
关键提示：
实际存储二叉树时，堆栈仅作为临时容器，若需持久化存储，应结合前序/中序遍历序列化到文件或数据库。
引用说明
- 算法设计参考《算法导论》深度优先遍历非递归实现
- Java Stack类文档：Oracle官方Java 17 Specifications
- 二叉树遍历理论：Stanford CS106B课程资料
通过堆栈实现二叉树遍历，开发者能精准控制内存使用，避免递归缺陷,尤其适合处理超大规模树结构数据。
原创文章，发布者：酷盾叔，转转请注明出处：https://www.kd.cn/ask/28879.html
