02.4.1.1 二叉树结构与递归遍历
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.1 二叉树与遍历
02.4.1.1-001 二叉树是什么结构?
一句话结论
二叉树是每个节点最多两个子节点(左孩子、右孩子)的树形层次结构;节点含值与左右指针;遍历分深度优先(前/中/后序)与广度优先(层序)。
概念解释
- 节点:值、left、right。
- 度:子节点个数。
- 层次:根为第 0 层,向下递增。
原理流程
- 根节点出发。
- 按左右分支递归。
- 空节点为递归基准。
代码 / 示例
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { val = v; }
}
常见误区
- 误区:二叉树节点必须有两个孩子;正解:孩子可为空。
- 误区:左右孩子无序等价;正解:左、右位置有区别。
追问
- Q:二叉树可以有环吗? A:标准定义无环,出现环按链表环处理。
- Q:n 节点二叉树有多少条边? A:n-1 条。
02.4.1.1-002 满二叉树、完全二叉树、平衡二叉树有什么区别?
一句话结论
满二叉树每层节点填满且叶子都在最底层;完全二叉树除最后一层外填满,最后一层节点靠左连续;平衡二叉树左右子树高度差不超过 1;三者定义角度不同。
概念解释
- 满:所有非叶子都有两孩子。
- 完全:层序编号不缺位。
- 平衡:高度差约束。
原理流程
- 按层序编号对照完全性。
- 比较子树高度判断平衡。
- 叶子位置判断满。
代码 / 图示
满: o
/ \
o o
完全: o
/ \
o o
/
o
常见误区
- 误区:完全二叉树就是满二叉树;正解:满是完全的特例。
- 误区:平衡二叉树要求完全;正解:只约束高度差。
追问
- Q:堆基于哪种二叉树? A:完全二叉树。
- Q:AVL 树平衡条件? A:左右子树高度差 ≤1 且子树平衡。
02.4.1.1-003 二叉树为什么常用指针而不是数组存?
一句话结论
链表式节点便于动态增删与任意形状;完全二叉树可用数组按层序编号存储,父子下标可公式定位;稀疏树用数组会浪费空间。
概念解释
- 指针:动态、形状任意。
- 数组:层序编号,适合完全树。
- 下标公式(0 起):父
(i-1)/2,左2i+1,右2i+2。
原理流程
- 完全树按层序填数组。
- 公式定位父子。
- 非完全树需存空位。
代码 / 图示
数组:[根, 左, 右, 左左, 左右, ...]
常见误区
- 误区:二叉树都能用紧凑数组;正解:稀疏形状有空洞。
- 误区:数组存树随机访问快就一定优;正解:动态增删指针更灵活。
追问
- Q:堆为什么用数组? A:堆是完全二叉树,无空洞。
- Q:二叉搜索树数组化? A:不平衡时空洞严重。
02.4.1.1-004 前序遍历递归怎么写?
一句话结论
根 → 左 → 右:先访问当前节点,再递归左子树、右子树;O(n) 时间,递归栈 O(h) 空间。
概念解释
- 前序:根在最前。
- 递归基准:空节点返回。
- 结果列表外部收集。
原理流程
- 空返回。
- 访问 root。
- 递归左、递归右。
代码 / 示例
void preorder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
常见误区
- 误区:先递归左再访问根;正解:前序根最先访问。
- 误区:忘记传结果列表;正解:外部收集或返回新列表。
追问
- Q:前序序列能唯一确定树吗? A:不能,需配合中序。
- Q:递归深度大怎么办? A:改迭代防栈溢出。
02.4.1.1-005 中序遍历递归怎么写?
一句话结论
左 → 根 → 右:递归左子树,访问当前节点,再递归右子树;BST 的中序结果严格递增。
概念解释
- 中序:根在中间。
- BST 性质:左 < 根 < 右。
- 递归顺序固定。
原理流程
- 空返回。
- 递归左。
- 访问 root,递归右。
代码 / 示例
void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
常见误区
- 误区:中序先访问根;正解:左子树走完才访问根。
- 误区:BST 中序可能重复;正解:重复值位置按定义,序列非严格递增。
追问
- Q:中序有序说明是 BST 吗? A:是必要条件,结合结构验证。
- Q:反序中序? A:先右后左得到降序。
02.4.1.1-006 后序遍历递归怎么写?
一句话结论
左 → 右 → 根:递归左右子树后访问当前节点;适合需要先处理子节点再汇总的问题(高度、直径、子树统计)。
概念解释
- 后序:根在最后。
- 子树先于根完成。
- 返回值汇总常用。
原理流程
- 空返回。
- 递归左、递归右。
- 访问 root。
代码 / 示例
void postorder(TreeNode root, List<Integer> res) {
if (root == null) return;
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
常见误区
- 误区:后序用来找路径从上到下;正解:后序自底向上。
- 误区:左右顺序可互换而不影响结果;正解:顺序约定左先右后。
追问
- Q:哪些题用后序返回值? A:高度、直径、子树和、LCA。
- Q:后序序列能单独定树吗? A:不能,需中序配合。
02.4.1.1-007 前序遍历迭代版怎么写?
一句话结论
栈模拟递归:压根后弹出访问,再按右、左顺序压栈(栈 LIFO 保证左先出);O(n) 时间 O(h) 栈空间。
概念解释
- 栈存待访问节点。
- 压栈顺序与遍历顺序相反。
- 右先压、左后压。
原理流程
- 根入栈。
- 弹出访问。
- 右孩子入栈,左孩子入栈。
代码 / 示例
List<Integer> preorder(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> st = new ArrayDeque<>();
if (root != null) st.push(root);
while (!st.isEmpty()) {
TreeNode cur = st.pop();
res.add(cur.val);
if (cur.right != null) st.push(cur.right);
if (cur.left != null) st.push(cur.left);
}
return res;
}
常见误区
- 误区:先压左后压右;正解:栈后进先出,右先压。
- 误区:空节点入栈;正解:入栈前判空。
追问
- Q:迭代前序与递归等价吗? A:访问顺序一致。
- Q:栈空间最坏多少? A:链状树 O(n)。
02.4.1.1-008 中序遍历迭代版怎么写?
一句话结论
一路向左压栈,走到底后弹出访问,再转向右子树;O(n) 时间 O(h) 空间。
概念解释
- 栈保存待回退的节点。
- 先深入左链。
- 弹出后处理右。
原理流程
- cur 非空则压栈并左移。
- 栈空停止;否则弹出访问,cur 转向右。
代码 / 示例
List<Integer> inorder(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) { st.push(cur); cur = cur.left; }
cur = st.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
常见误区
- 误区:循环条件只判栈空;正解:cur 可能非空而栈空。
- 误区:弹出后立即回左;正解:转向右子树。
追问
- Q:中序迭代栈深? A:树高 h。
- Q:BST 第 K 大中序? A:迭代数到第 K 个。
02.4.1.1-009 后序遍历迭代版怎么写?
一句话结论
两种常见写法:前序变体(根右左)结果反转得左右根;或栈中记录上次访问节点,右子树未处理前不回退根;O(n) 时间 O(h) 空间。
概念解释
- 变体法:根→右→左,反转即后序。
- 标记法:区分节点首次与二次出栈。
- 上次访问指针。
原理流程
- 变体:按根右左收集,最后反转列表。
- 标记:压根,先左;右处理完再访问根。
代码 / 示例
List<Integer> postorder(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
Deque<TreeNode> st = new ArrayDeque<>();
if (root != null) st.push(root);
while (!st.isEmpty()) {
TreeNode cur = st.pop();
res.addFirst(cur.val); // 根右左反转
if (cur.left != null) st.push(cur.left);
if (cur.right != null) st.push(cur.right);
}
return res;
}
常见误区
- 误区:直接照搬前序改访问位置;正解:后序需等子树完成。
- 误区:变体法忘记反转;正解:收集顺序与目标相反。
追问
- Q:标记法怎么判断右已访问? A:记录 last 指针对比。
- Q:后序迭代为什么更绕? A:根最后处理,需二次入栈或反转。
02.4.1.1-010 层序遍历(BFS)怎么写?
一句话结论
队列逐层扩展;每轮按当前队列长度处理一层,子节点入队;O(n) 时间 O(宽度) 空间。
概念解释
- 队列 FIFO 保证同层顺序。
- size 固定本层数量。
- 子节点入队。
原理流程
- 根入队。
- 循环取当前 size 遍历一层。
- 左右子节点入队。
代码 / 示例
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
level.add(cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
res.add(level);
}
return res;
}
常见误区
- 误区:不记 size 导致层交错;正解:每轮固定当前队长。
- 误区:子节点入队前不判空;正解:空节点不入队。
追问
- Q:锯齿层序? A:按层奇偶反转列表。
- Q:最大宽度? A:记录每层最左最右下标。
02.4.1.1-011 Morris 遍历原理是什么?
一句话结论
利用叶子空闲右指针构建临时前驱链接,走到左子树最右节点把其 right 连到当前节点,从而不用栈完成遍历;O(n) 时间 O(1) 空间,遍历后拆除临时链接。
概念解释
- 线索:空右指针作回退链。
- 前驱:左子树最右节点。
- 临时链接需恢复。
原理流程
- 当前无左孩子:访问后走右。
- 有左孩子:找左子树最右前驱。
- 前驱 right 为空则连当前,当前左移;否则拆除并访问当前,当前右移。
代码 / 图示
当前 cur
前驱 pred = 左子树最右
pred.right == null → 连 cur,cur = cur.left
pred.right == cur → 拆除,访问 cur,cur = cur.right
常见误区
- 误区:Morris 不修改树;正解:临时建链后必须拆除。
- 误区:找不到前驱死循环;正解:按右链走到 null 或 cur。
追问
- Q:Morris 空间为什么 O(1)? A:只用指针与临时变量,无栈。
- Q:工程常用吗? A:面试了解原理即可,递归/迭代更易维护。
02.4.1.1-012 二叉树最大深度(LC 104)怎么求?
一句话结论
后序递归:当前深度 = 1 + max(左深, 右深);空节点深度 0;O(n) 时间 O(h) 递归栈。
概念解释
- 深度:根到当前节点边数/层数口径按题目。
- 自底向上汇总。
- 基准空树 0。
原理流程
- 空返回 0。
- 递归求左右深度。
- 取最大加一。
代码 / 示例
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
常见误区
- 误区:层序求深度记层数与递归口径不一致;正解:统一边数或节点数口径。
- 误区:只递归一侧;正解:取左右最大。
追问
- Q:迭代求深度? A:BFS 层数或 DFS 栈记录深度。
- Q:最小深度? A:注意叶子才计数,不能直接取 min。
02.4.1.1-013 平衡二叉树判断(LC 110)怎么做?
一句话结论
后序返回子树高度,若左右高度差 >1 标记不平衡;自底向上一次遍历;O(n) 时间 O(h) 栈。
概念解释
- 平衡:|左高 - 右高| ≤ 1。
- 自底向上避免重复求高。
- 可用特殊返回值 -1 表示不平衡。
原理流程
- 空返回 0。
- 求左右高,任一不平衡返回 -1。
- 高差 >1 返回 -1,否则返回当前高。
代码 / 示例
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode root) {
if (root == null) return 0;
int l = height(root.left);
int r = height(root.right);
if (l == -1 || r == -1 || Math.abs(l - r) > 1) return -1;
return Math.max(l, r) + 1;
}
常见误区
- 误区:顶层求高再比较,重复遍历;正解:后序一次返回高度与平衡状态。
- 误区:空树不平衡;正解:空树平衡。
追问
- Q:AVL 失衡怎么旋转? A:见平衡树章节,四类旋转。
- Q:高度差口径? A:节点层数差,按实现统一。
02.4.1.1-014 二叉树直径(LC 543)怎么求?
一句话结论
直径为经过某节点的最长路径,长度 = 左高 + 右高;后序遍历中用全局变量记录左右高之和最大值;O(n) 时间 O(h) 栈。
概念解释
- 路径:不重复经过节点的边数。
- 拐点:路径最高处节点。
- 高度参与汇总。
原理流程
- 递归求左右高度。
- 更新直径候选
left+right。 - 返回当前子树高度。
代码 / 示例
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return ans;
}
private int depth(TreeNode root) {
if (root == null) return 0;
int l = depth(root.left);
int r = depth(root.right);
ans = Math.max(ans, l + r);
return Math.max(l, r) + 1;
}
常见误区
- 误区:直径等于最大深度;正解:直径是跨左右的路径。
- 误区:返回左右高之和;正解:返回子树高度供上层使用。
追问
- Q:直径按节点数怎么算? A:边数 +1,按题目口径。
- Q:路径一定过根吗? A:不一定,可在任一子树内。
02.4.1.1-015 路径总和(LC 112)怎么做?
一句话结论
前序递减目标值,到叶子时判断剩余是否为 0;任一叶子满足即返回 true;O(n) 时间 O(h) 栈。
概念解释
- 路径:根到叶子。
- 剩余:target 减已访问值。
- 叶子判定:左右都空。
原理流程
- 空返回 false。
- 扣减当前值。
- 叶子判断剩余,否则递归左右。
代码 / 示例
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
targetSum -= root.val;
if (root.left == null && root.right == null) return targetSum == 0;
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
常见误区
- 误区:非叶子也判剩余 0;正解:必须到叶子。
- 误区:扣减后未回溯;正解:值传递无需回溯。
追问
- Q:找出所有路径和(LC 113)? A:前序记录路径,叶子收集。
- Q:节点值可为负? A:不影响递归判定,不能提前剪枝。
02.4.1.1-016 二叉树所有路径(LC 257)怎么做?
一句话结论
前序回溯:当前路径追加节点值,到叶子拼接成串加入结果;返回上层移除最后一个节点;O(n) 时间 O(h) 栈。
概念解释
- 路径:根到叶子字符串。
- 回溯:离开子树撤销选择。
- 叶子收集。
原理流程
- 追加当前值。
- 叶子收集路径。
- 递归左右后回溯移除。
代码 / 示例
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root, new StringBuilder(), res);
return res;
}
private void dfs(TreeNode node, StringBuilder path, List<String> res) {
if (node == null) return;
int len = path.length();
if (len > 0) path.append("->");
path.append(node.val);
if (node.left == null && node.right == null) res.add(path.toString());
dfs(node.left, path, res);
dfs(node.right, path, res);
path.setLength(len);
}
常见误区
- 误区:字符串不可变无需回溯;正解:StringBuilder 复用需恢复长度。
- 误区:空节点也加入路径;正解:判空返回。
追问
- Q:路径和 II 类似框架? A:同前序回溯,叶子判断和。
- Q:回溯栈空间? A:O(h) 路径长度。
02.4.1.1-017 递归解题怎么判断用哪个遍历位置?
一句话结论
需要节点自身信息在前处理用前序,需要左中右顺序用中序,需要子树结果汇总用后序;先明确“当前节点要从子树拿什么”,再选遍历位置。
概念解释
- 前序:进入时处理。
- 中序:BST 顺序。
- 后序:汇总返回值。
原理流程
- 列出子树需返回的量。
- 选后序汇总;需顺序选中序。
- 定义基准与返回值。
代码 / 图示
高度/直径/LCA:后序
路径/构造:前序
有序性/第 K:中序
常见误区
- 误区:所有树题都套后序;正解:按信息依赖选位置。
- 误区:返回值与外部变量混用不清;正解:能返回值就不用全局变量。
追问
- Q:LCA 为什么后序? A:需知道左右是否命中目标。
- Q:序列化用哪种? A:前序便于重建。
02.4.1.1-018 递归与迭代怎么选型?
一句话结论
递归代码直观、贴近定义;深度过大有栈溢出风险;迭代用显式栈控制内存,适合深树;工程中先写递归确认正确性,深树再改迭代。
概念解释
- 调用栈:递归隐式占用。
- 显式栈:迭代可控。
- 深度阈值:运行时栈大小有限。
原理流程
- 评估树高。
- 浅层用递归。
- 深层改迭代或 Morris。
代码 / 图示
递归:简洁,栈 O(h)
迭代:显式栈 O(h)
Morris:O(1) 空间,复杂
常见误区
- 误区:递归一定更慢所以禁用;正解:常数可控,先读性后性能。
- 误区:迭代栈空间为 O(1);正解:仍是 O(h)。
追问
- Q:链状树递归深度? A:O(n),可能爆栈。
- Q:尾递归能优化吗? A:Java 不保证尾递归优化。
02.4.1.1-019 二叉树题有哪些边界用例?
一句话结论
空树、单节点、只有左链、只有右链、两节点、完全树、带负值节点;验证空判、叶子判定、递归基准与深度口径。
概念解释
- 空与最短。
- 退化链状。
- 值正负不影响结构判断。
原理流程
- 空树返回默认口径。
- 单节点走叶子分支。
- 链状检查栈深与终止。
代码 / 图示
null / [1] / [1,null,2] / 左链 / 右链
常见误区
- 误区:默认树非空;正解:入口判空。
- 误区:叶子判断只看一侧;正解:左右都空才是叶子。
追问
- Q:单节点路径和? A:节点值等于目标即成立。
- Q:空树直径? A:0。
02.4.1.1-020 二叉树遍历复杂度怎么汇报?
一句话结论
三种递归与迭代遍历均 O(n) 时间,栈/栈空间 O(h);层序 O(n) 时间 O(宽度);Morris O(n) 时间 O(1) 空间;n 为节点数,h 为树高。
概念解释
- 每节点访问常数次。
- 辅助空间按栈深或层宽。
- 平衡树 h=log n,链状 h=n。
原理流程
- 统计访问轮次。
- 标注栈/队列规模。
- 区分最坏树形。
代码 / 图示
递归遍历:O(n) / O(h)
层序:O(n) / O(宽度)
Morris:O(n) / O(1)
常见误区
- 误区:层序空间 O(n) 恒成立;正解:按最大层宽,平衡树 O(n),链状 O(1)。
- 误区:Morris 不花额外空间但修改节点;正解:临时指针空间 O(1),结构需恢复。
追问
- Q:前中后序能否 O(1) 空间? A:Morris 可以,代价是临时改指针。
- Q:n 节点树最小高度? A:平衡时 ceil(log2(n+1))。