罗罗编程学习记录
本页内容 展开查看

02.4.1.1 二叉树结构与递归遍历

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.1 二叉树与遍历

02.4.1.1-001 二叉树是什么结构?

一句话结论

二叉树是每个节点最多两个子节点(左孩子、右孩子)的树形层次结构;节点含值与左右指针;遍历分深度优先(前/中/后序)与广度优先(层序)。

概念解释

  • 节点:值、left、right。
  • 度:子节点个数。
  • 层次:根为第 0 层,向下递增。

原理流程

  1. 根节点出发。
  2. 按左右分支递归。
  3. 空节点为递归基准。

代码 / 示例

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;三者定义角度不同。

概念解释

  • 满:所有非叶子都有两孩子。
  • 完全:层序编号不缺位。
  • 平衡:高度差约束。

原理流程

  1. 按层序编号对照完全性。
  2. 比较子树高度判断平衡。
  3. 叶子位置判断满。

代码 / 图示

满:      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。

原理流程

  1. 完全树按层序填数组。
  2. 公式定位父子。
  3. 非完全树需存空位。

代码 / 图示

数组:[根, 左, 右, 左左, 左右, ...]

常见误区

  • 误区:二叉树都能用紧凑数组;正解:稀疏形状有空洞。
  • 误区:数组存树随机访问快就一定优;正解:动态增删指针更灵活。

追问

  • Q:堆为什么用数组? A:堆是完全二叉树,无空洞。
  • Q:二叉搜索树数组化? A:不平衡时空洞严重。

02.4.1.1-004 前序遍历递归怎么写?

一句话结论

根 → 左 → 右:先访问当前节点,再递归左子树、右子树;O(n) 时间,递归栈 O(h) 空间。

概念解释

  • 前序:根在最前。
  • 递归基准:空节点返回。
  • 结果列表外部收集。

原理流程

  1. 空返回。
  2. 访问 root。
  3. 递归左、递归右。

代码 / 示例

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 性质:左 < 根 < 右。
  • 递归顺序固定。

原理流程

  1. 空返回。
  2. 递归左。
  3. 访问 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 后序遍历递归怎么写?

一句话结论

左 → 右 → 根:递归左右子树后访问当前节点;适合需要先处理子节点再汇总的问题(高度、直径、子树统计)。

概念解释

  • 后序:根在最后。
  • 子树先于根完成。
  • 返回值汇总常用。

原理流程

  1. 空返回。
  2. 递归左、递归右。
  3. 访问 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) 栈空间。

概念解释

  • 栈存待访问节点。
  • 压栈顺序与遍历顺序相反。
  • 右先压、左后压。

原理流程

  1. 根入栈。
  2. 弹出访问。
  3. 右孩子入栈,左孩子入栈。

代码 / 示例

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) 空间。

概念解释

  • 栈保存待回退的节点。
  • 先深入左链。
  • 弹出后处理右。

原理流程

  1. cur 非空则压栈并左移。
  2. 栈空停止;否则弹出访问,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) 空间。

概念解释

  • 变体法:根→右→左,反转即后序。
  • 标记法:区分节点首次与二次出栈。
  • 上次访问指针。

原理流程

  1. 变体:按根右左收集,最后反转列表。
  2. 标记:压根,先左;右处理完再访问根。

代码 / 示例

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 固定本层数量。
  • 子节点入队。

原理流程

  1. 根入队。
  2. 循环取当前 size 遍历一层。
  3. 左右子节点入队。

代码 / 示例

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) 空间,遍历后拆除临时链接。

概念解释

  • 线索:空右指针作回退链。
  • 前驱:左子树最右节点。
  • 临时链接需恢复。

原理流程

  1. 当前无左孩子:访问后走右。
  2. 有左孩子:找左子树最右前驱。
  3. 前驱 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。

原理流程

  1. 空返回 0。
  2. 递归求左右深度。
  3. 取最大加一。

代码 / 示例

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 表示不平衡。

原理流程

  1. 空返回 0。
  2. 求左右高,任一不平衡返回 -1。
  3. 高差 >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) 栈。

概念解释

  • 路径:不重复经过节点的边数。
  • 拐点:路径最高处节点。
  • 高度参与汇总。

原理流程

  1. 递归求左右高度。
  2. 更新直径候选 left+right。
  3. 返回当前子树高度。

代码 / 示例

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 减已访问值。
  • 叶子判定:左右都空。

原理流程

  1. 空返回 false。
  2. 扣减当前值。
  3. 叶子判断剩余,否则递归左右。

代码 / 示例

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) 栈。

概念解释

  • 路径:根到叶子字符串。
  • 回溯:离开子树撤销选择。
  • 叶子收集。

原理流程

  1. 追加当前值。
  2. 叶子收集路径。
  3. 递归左右后回溯移除。

代码 / 示例

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 顺序。
  • 后序:汇总返回值。

原理流程

  1. 列出子树需返回的量。
  2. 选后序汇总;需顺序选中序。
  3. 定义基准与返回值。

代码 / 图示

高度/直径/LCA:后序
路径/构造:前序
有序性/第 K:中序

常见误区

  • 误区:所有树题都套后序;正解:按信息依赖选位置。
  • 误区:返回值与外部变量混用不清;正解:能返回值就不用全局变量。

追问

  • Q:LCA 为什么后序? A:需知道左右是否命中目标。
  • Q:序列化用哪种? A:前序便于重建。

02.4.1.1-018 递归与迭代怎么选型?

一句话结论

递归代码直观、贴近定义;深度过大有栈溢出风险;迭代用显式栈控制内存,适合深树;工程中先写递归确认正确性,深树再改迭代。

概念解释

  • 调用栈:递归隐式占用。
  • 显式栈:迭代可控。
  • 深度阈值:运行时栈大小有限。

原理流程

  1. 评估树高。
  2. 浅层用递归。
  3. 深层改迭代或 Morris。

代码 / 图示

递归:简洁,栈 O(h)
迭代:显式栈 O(h)
Morris:O(1) 空间,复杂

常见误区

  • 误区:递归一定更慢所以禁用;正解:常数可控,先读性后性能。
  • 误区:迭代栈空间为 O(1);正解:仍是 O(h)。

追问

  • Q:链状树递归深度? A:O(n),可能爆栈。
  • Q:尾递归能优化吗? A:Java 不保证尾递归优化。

02.4.1.1-019 二叉树题有哪些边界用例?

一句话结论

空树、单节点、只有左链、只有右链、两节点、完全树、带负值节点;验证空判、叶子判定、递归基准与深度口径。

概念解释

  • 空与最短。
  • 退化链状。
  • 值正负不影响结构判断。

原理流程

  1. 空树返回默认口径。
  2. 单节点走叶子分支。
  3. 链状检查栈深与终止。

代码 / 图示

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。

原理流程

  1. 统计访问轮次。
  2. 标注栈/队列规模。
  3. 区分最坏树形。

代码 / 图示

递归遍历: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))。