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

02.4.1.3 二叉树构造与变换

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

02.4.1.3-001 前序 + 中序构造二叉树(LC 105)怎么做?

一句话结论

前序首元素为根;在中序中定位根,左侧为左子树、右侧为右子树;按子树长度切分前序,递归构造左右;O(n) 时间 O(n) 哈希定位 + O(h) 栈。

概念解释

  • 前序定根。
  • 中序分左右。
  • 长度对齐切片。

原理流程

  1. 取前序首元素建根。
  2. 中序找根下标,切左右区间。
  3. 按长度切前序,递归左右。

代码 / 示例

private Map<Integer, Integer> inPos;
public TreeNode buildTree(int[] pre, int[] in) {
    inPos = new HashMap<>();
    for (int i = 0; i < in.length; i++) inPos.put(in[i], i);
    return build(pre, 0, pre.length - 1, 0, in.length - 1);
}
private TreeNode build(int[] pre, int pl, int pr, int il, int ir) {
    if (pl > pr) return null;
    TreeNode root = new TreeNode(pre[pl]);
    int k = inPos.get(root.val);
    int leftSize = k - il;
    root.left = build(pre, pl + 1, pl + leftSize, il, k - 1);
    root.right = build(pre, pl + leftSize + 1, pr, k + 1, ir);
    return root;
}

常见误区

  • 误区:前序右段起点算错;正解:左段长度 = 中序根下标 - 左边界。
  • 误区:用值遍历中序找根 O(n²);正解:哈希表 O(1) 定位。

追问

  • Q:序列有重复值能构造吗? A:不能唯一确定,映射歧义。
  • Q:为什么前序+中序可唯一确定? A:根位置与左右划分互补。

02.4.1.3-002 后序 + 中序构造二叉树(LC 106)怎么做?

一句话结论

后序末元素为根;中序定位根切左右;后序按子树长度切分,先构造右子树再左子树;思路与前序对称。

概念解释

  • 后序末尾是根。
  • 中序分左右。
  • 右子树在后序前段靠后位置。

原理流程

  1. 取后序末元素建根。
  2. 中序定位根切区间。
  3. 按长度切后序,递归左右。

代码 / 示例

private Map<Integer, Integer> inPos;
public TreeNode buildTree(int[] in, int[] post) {
    inPos = new HashMap<>();
    for (int i = 0; i < in.length; i++) inPos.put(in[i], i);
    return build(in, 0, in.length - 1, post, 0, post.length - 1);
}
private TreeNode build(int[] in, int il, int ir, int[] post, int pl, int pr) {
    if (pl > pr) return null;
    TreeNode root = new TreeNode(post[pr]);
    int k = inPos.get(root.val);
    int rightSize = ir - k;
    root.right = build(in, k + 1, ir, post, pr - rightSize, pr - 1);
    root.left = build(in, il, k - 1, post, pl, pr - rightSize - 1);
    return root;
}

常见误区

  • 误区:先构造左子树;正解:后序末尾向前,右子树先切。
  • 误区:后序区间长度与中序不一致;正解:两侧子树长度对应。

追问

  • Q:前序+后序能唯一构造吗? A:不能,左右子树分界有歧义。
  • Q:构造后中序校验? A:可遍历对比原序列。

02.4.1.3-003 按层序数组怎么构造二叉树?

一句话结论

层序数组按位置填节点,下标 0 起:左孩子 2i+1、右孩子 2i+2;用队列逐层挂接,空值占位;适合完全二叉树的数组表示。

概念解释

  • 层序编号。
  • 队列挂接孩子。
  • 空位用 null 标记。

原理流程

  1. 首元素建根入队。
  2. 依次取数组值建节点挂到队首孩子。
  3. 非空节点入队。

代码 / 图示

数组:[1,2,3,null,4]
队列逐层挂左右

常见误区

  • 误区:稀疏树数组无空位;正解:null 占位保证下标对应。
  • 误区:空节点也入队;正解:跳过 null 但占位位置保留。

追问

  • Q:层序 + 空标记能唯一确定树吗? A:可以,配合 null 位置。
  • Q:反序列化常用哪种遍历? A:前序带空标记更易递归重建。

02.4.1.3-004 翻转二叉树(LC 226)怎么做?

一句话结论

递归交换每个节点的左右孩子,再递归翻转左右子树;前序或后序均可;O(n) 时间 O(h) 栈。

概念解释

  • 交换指针。
  • 子树递归翻转。
  • 自顶向下或自底向上。

原理流程

  1. 空返回。
  2. 交换左右孩子。
  3. 递归翻转两侧。

代码 / 示例

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(left);
    return root;
}

常见误区

  • 误区:先递归再交换导致引用错乱;正解:先存原左孩子再交换。
  • 误区:只交换根节点;正解:每个节点都要翻转。

追问

  • Q:迭代翻转? A:栈/队列逐层交换孩子。
  • Q:翻转后中序有什么变化? A:左右镜像,序列反转。

02.4.1.3-005 对称二叉树(LC 101)怎么判断?

一句话结论

递归比较两子树:左的左对右的右、左的右对右的左,值相等且结构对称;O(n) 时间 O(h) 栈。

概念解释

  • 镜像:对称位置相等。
  • 双节点递归。
  • 空节点对称基准。

原理流程

  1. 比较两节点都空为真。
  2. 一空一非空为假。
  3. 值相等且外侧、内侧递归对称。

代码 / 示例

public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && isMirror(a.left, b.right)
        && isMirror(a.right, b.left);
}

常见误区

  • 误区:比较同一节点左右孩子值;正解:跨两棵子树镜像位置比较。
  • 误区:结构不对称但值相等判真;正解:空结构也要对称。

追问

  • Q:迭代判断? A:队列成对入队比较。
  • Q:对称树中序有何特征? A:回文,但需结合结构。

02.4.1.3-006 合并二叉树(LC 617)怎么做?

一句话结论

两节点都存在则值相加建新节点;一空则用另一棵子树;递归合并左右;O(min(n1,n2)) 时间,复用或新建节点按题意。

概念解释

  • 重叠:值相加。
  • 单侧存在:直接沿用。
  • 递归合并。

原理流程

  1. 都空返回 null。
  2. 一空返回另一节点。
  3. 相加建根,递归合并左右。

代码 / 示例

public TreeNode mergeTrees(TreeNode a, TreeNode b) {
    if (a == null) return b;
    if (b == null) return a;
    TreeNode root = new TreeNode(a.val + b.val);
    root.left = mergeTrees(a.left, b.left);
    root.right = mergeTrees(a.right, b.right);
    return root;
}

常见误区

  • 误区:修改原树节点值;正解:按题意可新建或复用,避免污染输入。
  • 误区:一侧空时递归另一侧为空;正解:直接挂另一侧子树。

追问

  • Q:合并后节点数? A:重叠部分相加,单侧部分保留。
  • Q:迭代合并? A:队列成对挂接。

02.4.1.3-007 二叉树展开为链表(LC 114)怎么做?

一句话结论

前序顺序拉成右链:递归处理左右,把左子树插到根与右子树之间,左指针置空;O(n) 时间 O(h) 栈;也可用 Morris 思路 O(1) 空间。

概念解释

  • 结果:右斜链,顺序同前序。
  • 左子树移到右侧。
  • 原右子树接在左子树末尾。

原理流程

  1. 递归展开左右。
  2. 保存原右子树。
  3. 左子树接右,左置空,末尾接原右。

代码 / 示例

public void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    TreeNode right = root.right;
    root.right = root.left;
    root.left = null;
    TreeNode cur = root;
    while (cur.right != null) cur = cur.right;
    cur.right = right;
}

常见误区

  • 误区:直接 root.right = root.left 丢失原右子树;正解:先保存。
  • 误区:左指针未置空;正解:结果链表左指针必须为空。

追问

  • Q:O(1) 空间做法? A:找左子树最右节点接原右,原地展开。
  • Q:展开顺序是哪种遍历? A:前序。

02.4.1.3-008 二叉树右视图(LC 199)怎么做?

一句话结论

层序遍历每层取最后一个节点;或 DFS 按根右左顺序,首次到达新深度记录节点;O(n) 时间 O(h)/O(宽度) 空间。

概念解释

  • 右视图:每层最右可见。
  • BFS 取层尾。
  • DFS 优先右子树。

原理流程

  1. BFS 逐层收集,加层尾。
  2. 或 DFS 深度等于结果长度时记录。

代码 / 示例

public List<Integer> rightSideView(TreeNode root) {
    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();
        TreeNode cur = null;
        for (int i = 0; i < size; i++) {
            cur = q.poll();
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        res.add(cur.val);
    }
    return res;
}

常见误区

  • 误区:只取根的右链;正解:右链缺失时左子树顶部可见。
  • 误区:DFS 先左后右也能取右视图;正解:需先右后左保证首达为最右。

追问

  • Q:左视图? A:对称取每层最左。
  • Q:DFS 深度口径? A:根深度 0 或 1,与结果长度对齐。

02.4.1.3-009 二叉树序列化与反序列化(LC 297)怎么做?

一句话结论

前序遍历带空标记序列化为字符串;反序列化按前序读值,空标记返回 null,递归建左右;O(n) 时间 O(n) 存储;需处理分隔与空值。

概念解释

  • 空标记:保证重建结构。
  • 前序便于递归还原。
  • 分隔符切分。

原理流程

  1. 序列化:前序拼接,空节点写标记。
  2. 反序列化:按序取值,建根递归左右。
  3. 指针/队列消费序列。

代码 / 示例

// 序列化
void serialize(TreeNode node, StringBuilder sb) {
    if (node == null) { sb.append("null,"); return; }
    sb.append(node.val).append(',');
    serialize(node.left, sb);
    serialize(node.right, sb);
}
// 反序列化
TreeNode deserialize(Deque<String> data) {
    String v = data.poll();
    if ("null".equals(v)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(v));
    root.left = deserialize(data);
    root.right = deserialize(data);
    return root;
}

常见误区

  • 误区:不带空标记反序列化;正解:无前序+中序无法唯一还原。
  • 误区:反序列化用数组下标未推进;正解:队列或全局指针消费。

追问

  • Q:层序序列化可行吗? A:可以,队列重建。
  • Q:节点值含分隔符? A:需转义或用固定宽度编码。

02.4.1.3-010 子树判断(LC 572)怎么做?

一句话结论

遍历主树每个节点,判断以其为根的子树是否与子树结构值完全一致;双递归:外层遍历,内层同构比较;O(n·m) 时间(可优化哈希)。

概念解释

  • 同构:结构与值全匹配。
  • 外层枚举根。
  • 内层递归比较。

原理流程

  1. 当前节点开始比较。
  2. 匹配返回真。
  3. 否则递归左右子树。

代码 / 示例

public boolean isSubtree(TreeNode root, TreeNode sub) {
    if (root == null) return sub == null;
    return isSame(root, sub) || isSubtree(root.left, sub) || isSubtree(root.right, sub);
}
private boolean isSame(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
}

常见误区

  • 误区:值部分相同即子树;正解:结构与整棵子树都要匹配。
  • 误区:空子树口径;正解:按题目约定,通常空树视为子树。

追问

  • Q:高效做法? A:树哈希序列化后字符串匹配。
  • Q:子结构与子树区别? A:子结构允许主树裁剪节点,匹配更宽松。

02.4.1.3-011 填充二叉树右侧节点指针(LC 116/117)怎么做?

一句话结论

层序遍历把同层节点依次串联 next;完美二叉树(116)也可递归利用父节点指针连接兄弟与堂兄弟;O(n) 时间 O(宽度) 或 O(h) 空间。

概念解释

  • next:同层右侧节点。
  • 层序天然按层。
  • 完美树可跨子树连接。

原理流程

  1. 队列逐层处理。
  2. 层内相邻节点连 next。
  3. 层尾 next 置空。

代码 / 示例

public Node connect(Node root) {
    if (root == null) return null;
    Queue<Node> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node cur = q.poll();
            if (i + 1 < size) cur.next = q.peek();
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
    }
    return root;
}

常见误区

  • 误区:只连亲兄弟;正解:堂兄弟也需 next 串联。
  • 误区:层尾 next 残留;正解:层尾置空。

追问

  • Q:常数空间做法? A:利用上层 next 链遍历下层,见完美二叉树题解。
  • Q:非完美树(117)? A:层序最稳妥。

02.4.1.3-012 普通二叉树最近公共祖先(LC 236)怎么做?

一句话结论

后序递归:左右分别查找 p、q;左右都命中则当前为 LCA;一侧命中则向上返回该侧结果;O(n) 时间 O(h) 栈。

概念解释

  • 后序汇总命中情况。
  • 分叉点即 LCA。
  • 命中当前直接返回。

原理流程

  1. 空或命中当前返回当前。
  2. 递归左右。
  3. 两侧非空返回当前,否则返回非空侧。

代码 / 示例

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

常见误区

  • 误区:找到 p 就停止上溯;正解:需确认 q 在哪一侧。
  • 误区:p 是 q 祖先的情况;正解:命中当前直接返回,祖先即答案。

追问

  • Q:带 parent 指针怎么做? A:转两链表相交问题。
  • Q:多次查询 LCA? A:预处理倍增表,O(log n) 查询。

02.4.1.3-013 怎么找根到某节点的路径?

一句话结论

前序回溯记录路径,命中目标时复制路径返回;未命中回溯撤销;O(n) 时间 O(h) 路径空间。

概念解释

  • 路径:根到目标节点链。
  • 回溯:离开子树撤销。
  • 命中收集。

原理流程

  1. 路径压当前节点。
  2. 命中复制返回。
  3. 递归左右失败后弹出。

代码 / 示例

boolean dfs(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) return false;
    path.add(node);
    if (node == target) return true;
    if (dfs(node.left, target, path) || dfs(node.right, target, path)) return true;
    path.remove(path.size() - 1);
    return false;
}

常见误区

  • 误区:命中后未复制路径;正解:后续回溯会修改列表。
  • 误区:空节点入路径;正解:判空返回。

追问

  • Q:两节点路径求 LCA? A:两路径比对最后公共节点。
  • Q:路径和类题? A:同前序回溯框架。

02.4.1.3-014 前序 + 后序为什么不能唯一确定二叉树?

一句话结论

前序首与后序尾都是根,但左右子树分界无法从两种序列确定;当某节点只有一个孩子时,无法判断是左还是右,形态不唯一。

概念解释

  • 缺中序划分。
  • 单子树方向歧义。
  • 多解并存。

原理流程

  1. 根可定位。
  2. 左右长度分界不明。
  3. 单子树方向可左可右。

代码 / 图示

前序 [1,2] 后序 [2,1]
2 可作左孩子,也可作右孩子

常见误区

  • 误区:前序后序足以重建;正解:必须配合中序。
  • 误区:完美二叉树也有歧义;正解:完美树无单子树时可确定。

追问

  • Q:什么序列组合唯一? A:前序+中序、后序+中序。
  • Q:层序带空标记? A:可唯一重建。

02.4.1.3-015 树变换题怎么避免指针错乱?

一句话结论

修改指针前先保存被覆盖的引用(原右孩子、原左孩子);先接好新链接再断开旧链接;变换后检查左指针置空与尾部收尾。

概念解释

  • 引用保存。
  • 链接顺序。
  • 收尾检查。

原理流程

  1. 保存关键旧引用。
  2. 重连两侧。
  3. 清理残留指针。

代码 / 图示

保存 right → 挂 left → 左置空 → 末尾接 right

常见误区

  • 误区:直接覆盖导致子树丢失;正解:先存引用。
  • 误区:变换后残留旧 next/left;正解:结果链收尾置空。

追问

  • Q:怎么验证变换正确? A:遍历对比目标序列。
  • Q:原地修改会影响输入吗? A:会,按题意确认是否可改原树。

02.4.1.3-016 构造题的区间下标怎么切分?

一句话结论

用子树长度对齐两个序列:左子树长度由中序根位置算出,前序/后序按长度切片;四个边界下标(左右区间)同步推进,越界返回空。

概念解释

  • 长度对齐。
  • 双序列区间。
  • 越界基准。

原理流程

  1. 中序根下标 k。
  2. 左长 = k - 左界。
  3. 前/后序按长度切左右段。

代码 / 图示

中序:[il, k-1] 左 / [k+1, ir] 右
前序:左 [pl+1, pl+左长],右接后

常见误区

  • 误区:左右边界下标越界未判;正解:l > r 返回 null。
  • 误区:右段起点漏加左长;正解:长度对齐是关键。

追问

  • Q:下标溢出风险? A:用 l + (r-l)/2 类写法防溢出。
  • Q:递归栈深? A:O(h),退化链 O(n)。

02.4.1.3-017 树与双向链表互转是什么思路?

一句话结论

中序遍历有序,把 BST 转成有序双向链表:前驱接左、后继接右;遍历中维护上一个节点;头尾相连按题目要求;O(n) 时间 O(h) 栈。

概念解释

  • 中序有序。
  • 双向链接。
  • 前驱指针维护。

原理流程

  1. 中序递归。
  2. 上一节点右连当前,当前左连上一。
  3. 更新前驱。

代码 / 图示

prev ↔ cur

常见误区

  • 误区:先转数组再建链表;正解:可遍历中直接串联。
  • 误区:头尾未处理;正解:记录链表头与尾。

追问

  • Q:循环双向链表? A:头尾互指。
  • Q:非 BST 能转有序链表吗? A:需先排序。

02.4.1.3-018 构造与变换题有哪些边界用例?

一句话结论

空序列、单节点、只有左子树、只有右子树、两节点、完全树、重复值(构造题不允许);验证区间越界、空标记与指针收尾。

概念解释

  • 空与最短。
  • 退化单侧。
  • 等值歧义。

原理流程

  1. 空序列返回 null。
  2. 单节点直接建根。
  3. 单侧树检查切片方向。

代码 / 图示

[] / [1] / 仅左 / 仅右

常见误区

  • 误区:输入含重复值仍按唯一构造;正解:题目通常保证无重复。
  • 误区:变换空树报错;正解:入口判空返回。

追问

  • Q:两节点镜像? A:对称判断两侧值与空结构。
  • Q:序列化空树? A:序列化为空标记串。

02.4.1.3-019 构造与变换复杂度怎么汇报?

一句话结论

构造每节点一次 O(n) 时间,递归栈 O(h),哈希定位 O(n) 空间;变换类 O(n) 时间 O(h) 栈;序列化存储 O(n);子树朴素匹配 O(n·m)。

概念解释

  • 每节点常数次访问。
  • 栈深按树高。
  • 匹配类双递归相乘。

原理流程

  1. 统计节点访问次数。
  2. 标注栈与存储。
  3. 匹配题标注双树规模。

代码 / 图示

构造:O(n) / O(h) 栈 + O(n) 哈希
变换:O(n) / O(h)
子树匹配:O(n·m)

常见误区

  • 误区:构造用哈希定位仍报 O(n²);正解:哈希后定位 O(1),整体 O(n)。
  • 误区:变换空间 O(1);正解:递归栈 O(h)。

追问

  • Q:子树匹配哈希优化? A:树哈希后 O(n+m) 量级。
  • Q:序列化字符串大小? A:O(n),含空标记。

02.4.1.3-020 构造与变换常见变体有哪些?

一句话结论

前/后序 + 中序构造、层序重建、翻转、对称判断、合并、拉平链表、右视图、next 指针、序列化、子树判断、LCA;主线是遍历顺序选择与指针重连。

概念解释

  • 构造:序列还原结构。
  • 变换:指针重连。
  • 判断:双树递归比较。

原理流程

  1. 识别题目属于构造/变换/判断。
  2. 选对应遍历顺序。
  3. 套用递归框架。

代码 / 图示

构造:序列 + 递归切片
变换:保存引用 + 重连
判断:双节点递归比较

常见误区

  • 误区:变体题脱离遍历框架硬写;正解:先定遍历位置。
  • 误区:修改输入树未说明;正解:原地变换需确认题意。

追问

  • Q:哪类题必须层序? A:按层输出、同层串联。
  • Q:哪类题必须后序? A:需子树汇总结果。