⚡二叉树遍历 java 完全指南
在二叉树遍历 java体系中,掌握前序、中序、后序、层序是数据结构核心。本攻略聚焦递归与非递归实现,结合栈与队列,深度剖析遍历逻辑。
〈 前序遍历 〉根→左→右
📌 递归思路
访问根节点,再递归左子树,最后右子树。preOrder(root) 简洁直观。
⚙️ 非递归(栈)
使用Stack,先压入右孩子再左孩子,保证左先出。
| 遍历顺序 | 示例节点 | java关键代码 |
|---|---|---|
| 根→左→右 | A B D E C F | stack.push(root); |
二叉树遍历 java 前序常用于序列化/克隆树结构。
〔 中序遍历 〕左→根→右
◣ 递归中序:先左子树,访问根,再右子树。对于二叉搜索树BST,中序遍历得到有序序列。
示例:inorder(node.left); print(node); inorder(node.right);
◤ 迭代借助栈:持续向左深入,弹出访问后转向右节点。二叉树遍历 java面试高频考点。
- ① 当前节点不为空或栈非空循环
- ② 左链入栈
- ③ 弹出访问,指针移向右
◥ Morris遍历利用空闲指针,空间O(1)。建立前驱节点的右线索,实现中序。
〈 核心 〉若前驱右指针为空,则指向当前,并向左移动;否则恢复并访问。
》 后序遍历 左→右→根
后序在二叉树遍历 java中用于删除节点或表达式树计算。非递归较复杂,常用双栈或标记法。
※ 应用场景:计算目录大小、表达式树求值。
「 层序遍历 」BFS广度优先
使用Queue实现逐层访问。二叉树遍历 java中层序常用于求树深度、右视图等。
📊 层序遍历结果:A → B C → D E F G (逐层)
〖 网友们还关心 〗二叉树遍历 java 热点
⚡递归如何转为迭代?
递归本质是系统栈,模拟时使用Stack保存状态。前序相对简单,中序需控制访问时机,后序需额外标记。
◈ 通用模板:while(!stack.isEmpty() || node!=null) 控制循环。
⏱️ 遍历时间复杂度
所有遍历均O(n),每个节点访问一次。递归空间O(h),最坏O(n);Morris空间O(1)。
〈 二叉树遍历 java 〉性能对比:Morris > 迭代 > 递归(栈深度)。
📌 遍历实际应用
▪ 前序:目录列表、克隆
▪ 中序:BST排序输出
▪ 后序:删除文件夹、表达式
▪ 层序:最短路径、序列化
🧬 序列化与反序列化
常采用前序或层序。使用特殊标记null节点,如"#,"表示空。
java示例:serialize(root) → "1,2,#,#,3,4,#,#,5,#,#"
🔍 二叉树遍历 java 周边核心
🌲 树节点定义
class TreeNode { int val; TreeNode left, right; } 是基础。
📚 遍历变体
垂序遍历、ZigZag遍历、边界遍历等均基于二叉树遍历 java扩展。
※ 掌握四种遍历后,可轻松应对二叉树遍历 java相关算法题,如最近公共祖先、路径总和。
Ⅳ 深度示例:遍历推导与代码片段
给定二叉树:A(B(D,E),C(F,G)),前序:A B D E C F G;中序:D B E A F C G;后序:D E B F G C A。
| 遍历方式 | 递归实现(java) | 非递归核心 |
|---|---|---|
| 前序 | print(root); pre(left); pre(right); | Stack push right then left |
| 中序 | in(left); print; in(right); | 左链入栈 |
| 后序 | post(left); post(right); print; | 双栈/prev标记 |
☑️ 二叉树遍历 java 面试常要求手写非递归中序、层序打印每层节点。
🔄 迭代器模式与遍历
设计二叉搜索树迭代器,本质是中序遍历的受控版本。使用栈模拟递归,next()平均O(1)。
- ⚡ hasNext()
- ⚡ next()返回最小
- ⚡ 栈维护路径
- ⚡ 空间O(h)