Go back

LeetCode Hot 100——二叉树篇（遍历、深度、最近公共祖先）

LeetCode Hot 100 · 二叉树篇

二叉树是 Hot 100 里题量最大的一类（本篇 15 题），也是大厂手撕出现频率最高的数据结构。它的核心套路其实只有两个：遍历（前/中/后/层序，决定”何时处理当前节点”）和后序自底向上聚合（每个节点向上返回一个”单侧贡献”，同时用全局变量更新答案）。吃透这两条主线，15 题几乎可以一把梭。

约定：本文所有代码均使用 LeetCode 标准节点定义，类名 Solution，可直接提交编译：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val; this.left = left; this.right = right;
    }
}

#94 二叉树的中序遍历

题意

给定二叉树根节点 root，返回**中序遍历（左-根-右）**的节点值列表。题目同族还包括前序（根-左-右）、后序（左-右-根）。

输入：root = [1,null,2,3]
输出：[1,3,2]

题目本质：前/中/后序只是”处理当前节点值”的时机不同（先处理、中间处理、最后处理），DFS 框架完全相同。现实类比：读一本书——前序是先读标题再读内容，中序是读完左半本再读标题再读右半本，后序是读完全书内容再看标题索引。

难点与易错点

解法一：递归（直观）

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }

    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) return;   // 递归出口

        // 中序：左 → 根 → 右
        // 前序把 result.add 移到最前面，后序移到最后面
        dfs(node.left, result);     // 1. 遍历左子树
        result.add(node.val);       // 2. 处理当前节点
        dfs(node.right, result);    // 3. 遍历右子树
    }
}

解法二：迭代（显式栈，最优）

用 Deque 手动模拟递归栈，避免递归深度问题，也便于扩展（如按需暂停）。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        // 中序：一路压入最左侧链，弹栈访问，再转右子树
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {        // 1. 一路向左，把左侧链全部压栈
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();           // 2. 弹栈访问（此时左子树已处理完）
            result.add(cur.val);
            cur = cur.right;             // 3. 转向右子树
        }
        return result;
    }
}

复杂度逐步推导：每个节点恰好进栈一次、出栈一次，进出栈合计 2n 次操作，每次 O(1)，因此总时间 = 2n · O(1) = O(n)。空间上，栈里最多同时存放”从根到当前节点的最左侧链”，其长度等于树高 h，因此空间 = O(h)，最坏退化链表 = O(n)。

进阶：Morris 遍历利用空闲指针线索化，空间可以压到 O(1)（时间仍 O(n)），字节/美团进阶面偶尔追问，了解思路即可。

多解法对比

解法时间空间适用场景
递归O(n)O(h)面试首选，代码最短、最不易错
迭代（栈）O(n)O(h)树很深怕栈溢出，或需要”暂停/恢复”遍历时
MorrisO(n)O(1)极度受限内存、且会破坏树结构（需还原）的场合

为什么选递归：本题约束没有栈溢出风险，递归最简洁、最稳，是手撕正解；面试官若追问”不用递归呢”，再上迭代。

CodeTop 变体

#104 二叉树的最大深度

题意

给定二叉树根节点，返回其最大深度（根节点到最远叶节点路径上的节点数）。

输入：root = [3,9,20,null,null,15,7]
输出：3

题目本质：BFS 层序计数（每遍历完一层计数加一），或 DFS 递归 max(left, right) + 1。现实类比：统计大楼层数——BFS 像坐电梯逐层数，DFS 像爬楼梯到底再回传高度。

难点与易错点

解法一：递归 DFS（直观）

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;              // 空树深度为 0
        int left  = maxDepth(root.left);         // 左子树深度
        int right = maxDepth(root.right);        // 右子树深度
        return Math.max(left, right) + 1;        // 取较大侧 + 当前层
    }
}

解法二：BFS 层序（最优 / 源材料主解）

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        int depth = 0;

        while (!deque.isEmpty()) {
            int levelSize = deque.size();   // 当前层节点数

            // 处理当前层的所有节点
            while (levelSize-- > 0) {
                TreeNode node = deque.poll();
                if (node.left  != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }

            depth++;                        // 每处理完一层，深度加一
        }

        return depth;
    }
}

复杂度逐步推导：BFS 每个节点入队一次、出队一次，进出队合计 2n 次操作，每次 O(1)，时间 = O(n)。队列里最多同时存放”最宽一层的所有节点”，其数量为树宽 w（满二叉树最后一层可达 n/2），因此空间 = O(w)，最坏 O(n)。

多解法对比

解法时间空间适用场景
递归 DFSO(n)O(h)代码最短，面试首选
BFS 层序O(n)O(w)宽树比 DFS 省栈；且能顺便输出”每层”信息
DFS 显式栈O(n)O(h)怕递归栈溢出时

为什么选 BFS：层序遍历是”按层”问题的母模板，本题用它既直观又能直接复用 102/199 的框架，面试讲起来最有体系；DFS 版本作为一行式答案背下来即可。

CodeTop 变体

#226 翻转二叉树

题意

给定二叉树根节点，翻转整棵树（左右子树互换），返回翻转后的根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

题目本质：后序递归——先翻转左右子树，再交换当前节点的左右指针（后序保证子树已翻转完毕）。现实类比：做镜像照片——先把照片左右两半分别做镜像，再把两半互换位置。

难点与易错点

解法一：递归后序（直观 / 源材料主解）

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;   // 空树直接返回

        // 后序：先递归翻转子树，再交换
        invertTree(root.left);
        invertTree(root.right);

        // 交换当前节点的左右子树
        TreeNode tmp = root.left;
        root.left   = root.right;
        root.right  = tmp;

        return root;
    }
}

解法二：迭代 BFS（优化）

用队列广度遍历，边出队边交换，避免递归栈。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);

        while (!deque.isEmpty()) {
            TreeNode node = deque.poll();

            // 交换左右子树
            TreeNode tmp = node.left;
            node.left    = node.right;
            node.right   = tmp;

            if (node.left  != null) deque.offer(node.left);
            if (node.right != null) deque.offer(node.right);
        }
        return root;
    }
}

复杂度逐步推导：每个节点恰好出队一次、交换一次，进出队合计 2n 次 O(1) 操作，时间 = O(n)。队列最多容纳最宽一层的 w 个节点，空间 = O(w)，最坏满二叉树最后一层 = O(n)。相比递归版，最坏空间仍 O(n)，但不依赖调用栈，退化链式结构下更安全。

多解法对比

解法时间空间适用场景
递归后序O(n)O(h)面试首选，3 行搞定
迭代 BFSO(n)O(w)怕栈溢出 / 树极深时

为什么选递归：翻转本质是后序遍历，递归最贴合语义、最不易错；只有树极端深时才考虑迭代。

CodeTop 变体

#101 对称二叉树

题意

给定二叉树根节点，判断它是否轴对称（镜像对称）。

输入：root = [1,2,2,3,4,4,3]
输出：true

题目本质：双指针递归比较镜像关系——左子树的左 vs 右子树的右（外侧）、左子树的右 vs 右子树的左（内侧）。现实类比：检验蝴蝶翅膀——从中轴线两边同时展开，左翅每个点都要和右翅对应点一模一样。

难点与易错点

解法一：递归双指针（直观 / 源材料主解）

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;   // 都空：对称
        if (left == null || right == null) return false;  // 一空：不对称
        if (left.val != right.val) return false;          // 值不等：不对称

        // 递归检查镜像位置：
        // 外侧：左子树的左孩子 vs 右子树的右孩子
        // 内侧：左子树的右孩子 vs 右子树的左孩子
        return isMirror(left.left, right.right)
            && isMirror(left.right, right.left);
    }
}

解法二：迭代队列（优化）

成对入队，逐对比较，避免递归栈。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root.left);
        deque.offer(root.right);

        while (!deque.isEmpty()) {
            TreeNode left  = deque.poll();
            TreeNode right = deque.poll();

            if (left == null && right == null) continue;   // 都空，继续下一对
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;

            // 成对入队：外侧一对、内侧一对
            deque.offer(left.left);
            deque.offer(right.right);
            deque.offer(left.right);
            deque.offer(right.left);
        }
        return true;
    }
}

复杂度逐步推导：每对镜像节点恰好入队一次、出队一次，共 n/2 对节点、n 次进出队操作，时间 = O(n)。队列最多同时存放”最宽一层的节点对”，约为树宽 w 的两倍，空间 = O(w)，最坏 O(n)。

多解法对比

解法时间空间适用场景
递归双指针O(n)O(h)面试首选，语义最清晰
迭代队列O(n)O(w)树极深时替代递归

为什么选递归：对称判断本质就是”两指针递归镜像”，递归写法与”镜像”定义一一对应，最不容易写错。

CodeTop 变体

#543 二叉树的直径

题意

给定二叉树，返回其直径——任意两节点间最长路径的边数，路径可以不经过根节点。

输入：root = [1,2,3,4,5]
输出：3   （路径 [4,2,1,3] 或 [5,2,1,3]）

题目本质：DFS 后序——每个节点的直径贡献 = 左子树最大深度 + 右子树最大深度，返回值是”单侧最大深度”（供父节点用）。现实类比：找最长公路——每个城市统计”通过自己的最长路 = 左边最长路 + 右边最长路”，同时回报上级”我这一侧可借用的最长路段”。

难点与易错点

解法一：朴素双重计算（暴力）

对每个节点都调用一次 depth 求子树高度，再拼左右高度更新直径。depth 本身 O(n)，被 n 个节点重复调用。

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int throughRoot = depth(root.left) + depth(root.right);  // 经过根的直径
        int left  = diameterOfBinaryTree(root.left);             // 左子树内部直径
        int right = diameterOfBinaryTree(root.right);            // 右子树内部直径
        return Math.max(throughRoot, Math.max(left, right));
    }

    // 求子树高度：每个节点都被重复遍历，导致 O(n^2)
    private int depth(TreeNode node) {
        if (node == null) return 0;
        return Math.max(depth(node.left), depth(node.right)) + 1;
    }
}

解法二：后序一次遍历（最优 / 源材料主解）

class Solution {
    private int maxDiameter = 0; // 全局最大直径

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    // 返回以 root 为根的子树最大深度，同时更新全局直径
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth  = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // 经过当前节点的最长路径 = 左深度 + 右深度（边数）
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // 返回给父节点可用的最大深度（单侧）
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

复杂度逐步推导：一次后序遍历，每个节点恰好访问一次，每个节点内部只做常数次 Math.max 运算，因此总时间 = n · O(1) = O(n)（对比暴力版：把 n 次 O(n) 的深度计算合并进同一次遍历，省掉了 n 倍的重复）。空间 = 递归栈深度 = 树高 h → O(h)，最坏退化链表 O(n)。

💭 思考：为什么直径要「递归返回单侧深度 + 全局变量更新答案」？——先看暴力版病在哪：对每个节点都调一次 depth 求子树高度，同一个子树的高度被反复算，O(n²)。关键认知是「直径 = 左深度 + 右深度」，而深度本身就是递归能带回来的东西。于是让递归函数只返回「单侧最大深度」供父节点用，同时顺手用 leftDepth + rightDepth 更新全局答案——一次遍历就把深度复用起来。看到「路径/直径/最大路径和」这类「可以跨过某节点拼接」的题，就该想到这个「返回单侧 + 全局更新」的后序模板。

多解法对比

解法时间空间适用场景
朴素双重计算O(n²)O(h)仅作思路铺垫，不可用于面试
后序一次遍历O(n)O(h)面试标准解，复用深度返回值

为什么选后序一次遍历：本题 n 可达 10⁴，O(n²) 会超时；而”后序返回单侧 + 全局更新答案”是处理所有”路径/直径”类问题的通用模板，一次遍历即可完成。

CodeTop 变体

#102 二叉树的层序遍历

题意

给定二叉树根节点，返回层序遍历结果（从上到下、每层从左到右，逐层分组）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

题目本质：BFS + 按层分组——每层开始先记录当前层节点数 len，处理完 len 个节点即进入下一层。现实类比：学校按年级点名——先点完一年级所有人，再点二年级，每个年级的名字收集到一个子列表。

难点与易错点

解法一：BFS 队列（直观 / 源材料主解）

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);

        while (!deque.isEmpty()) {
            int levelSize = deque.size();       // 当前层节点数
            List<Integer> levelList = new ArrayList<>();

            // 处理当前层的所有节点
            while (levelSize-- > 0) {
                TreeNode node = deque.poll();
                levelList.add(node.val);

                if (node.left  != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }

            result.add(levelList);
        }
        return result;
    }
}

解法二：DFS 带层号（优化）

递归时携带层号 level，首次到达某层就 new 一个列表，按层号把节点追加进去。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) return;

        // 首次到达该层：新建一层的列表
        if (result.size() == level) result.add(new ArrayList<>());
        result.get(level).add(node.val);

        dfs(node.left,  level + 1, result);
        dfs(node.right, level + 1, result);
    }
}

复杂度逐步推导：DFS 每个节点访问一次，时间 = O(n)。空间 = 递归栈深度 = 树高 h → O(h)，最坏退化链表 O(n)；在”深而窄”的树上，其空间比 BFS 的 O(w) 更省。

多解法对比

解法时间空间适用场景
BFS 队列O(n)O(w)面试首选，直观且能直接复用到右视图/锯齿形
DFS 带层号O(n)O(h)树深而窄时更省空间

为什么选 BFS：层序遍历是 BFS 的教科书应用，levelSize 快照技巧是”按层处理”问题的通用钥匙，面试讲 BFS 最贴合题意。

CodeTop 变体

#108 将有序数组转换为二叉搜索树

题意

给定一个升序整数数组 nums，将它转换为一棵高度平衡的二叉搜索树（左右子树高度差不超过 1）。

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]   （一种合法答案即可）

题目本质：递归二分建树——每次取中间元素作根，左半段递归建左子树，右半段建右子树。现实类比：二分查找排书架——选书架正中间那本书作”根书”，左边书递归组成左子书架，右边书组成右子书架。

难点与易错点

解法一：数组拷贝（暴力 / 直观）

每次用 Arrays.copyOfRange 拷贝左右子数组，代码直观但反复拷贝。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;

        int mid = nums.length / 2;              // 取中点作根
        TreeNode root = new TreeNode(nums[mid]);

        // 每次拷贝左右子数组：单层拷贝 O(n)，共 log n 层 → O(n log n)
        root.left  = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
        return root;
    }
}

解法二：索引递归（最优 / 源材料主解）

不拷贝数组，只传左右边界索引，直接复用原数组。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length);
    }

    // 左闭右开区间 [l, r)
    private TreeNode buildBST(int[] nums, int l, int r) {
        if (l >= r) return null;              // 区间为空

        // 取中点作根，位运算防整数溢出
        int mid = l + ((r - l) >> 1);
        TreeNode root = new TreeNode(nums[mid]);

        root.left  = buildBST(nums, l, mid);      // 左半段 [l, mid)
        root.right = buildBST(nums, mid + 1, r);  // 右半段 [mid+1, r)

        return root;
    }
}

复杂度逐步推导：每个数组元素恰好被访问一次、恰好建一个节点，n 个元素建 n 个节点，每个节点 O(1) 建树，时间 = n · O(1) = O(n)。空间上只使用递归调用栈，栈深度 = 平衡树高 = O(log n)（因为每次严格二分，树是平衡的，不会退化）。

多解法对比

解法时间空间适用场景
数组拷贝O(n log n)O(n log n)仅直观理解，不可用于面试
索引递归O(n)O(log n)面试标准解，无额外数组

为什么选索引递归：题面 n 可达 10⁴，拷贝法的时间和空间都劣化，而索引法既不拷贝又保证平衡，是唯一正解。

CodeTop 变体

#98 验证二叉搜索树

题意

给定二叉树根节点，判断它是否是有效的 BST——每个节点左子树所有值严格小于它、右子树所有值严格大于它。

输入：root = [2,1,3]
输出：true

题目本质：上下界递归约束——每个节点都有一个合法值域 (lower, upper)，递归时向下收紧边界。现实类比：审查档案——每个文件夹内容必须落在父级设定的范围内，进左子文件夹收紧上界，进右子文件夹收紧下界。

难点与易错点

解法一：中序收集数组（暴力 / 直观）

BST 的中序遍历必然严格升序，收集后逐个检查。

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        for (int i = 1; i < values.size(); i++) {
            if (values.get(i) <= values.get(i - 1)) return false; // 必须严格升序
        }
        return true;
    }

    private void inorder(TreeNode node, List<Integer> values) {
        if (node == null) return;
        inorder(node.left, values);
        values.add(node.val);
        inorder(node.right, values);
    }
}

解法二：递归上下界（最优 / 源材料主解）

class Solution {
    public boolean isValidBST(TreeNode root) {
        // 初始上下界为 long 极值，防止 int 边界节点的误判
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long lower, long upper) {
        if (node == null) return true;

        // 当前节点值必须严格落在 (lower, upper) 内
        if (node.val <= lower || node.val >= upper) return false;

        // 左子树上界收紧为当前值；右子树下界收紧为当前值
        return validate(node.left, lower, node.val)
            && validate(node.right, node.val, upper);
    }
}

复杂度逐步推导：每个节点恰好访问一次，每个节点做 O(1) 次比较与两次递归调用，总时间 = n · O(1) = O(n)。空间只依赖递归栈，深度 = 树高 h → O(h)，最坏退化链表 O(n)（对比中序数组法的 O(n) 额外数组，这里省掉了整棵树的中序存储）。

💭 思考：为什么验证 BST 必须「传上下界」，而不能只比较当前节点和左右孩子？——看反例 [5,1,4,null,null,3,6]：3 在 5 的右子树里却小于 5，只比直接子节点（3 < 4 是合法的）就漏掉了。BST 的约束是「整棵子树都落在界内」，不是「局部父子关系」。于是把每个节点的合法值域 (lower, upper) 作为参数向下收紧——进左子树上界收紧为当前值，进右子树下界收紧为当前值。看到「判断整棵树满足某个全局性质」时，就该想到「把约束作为参数一路传下去」，而不是只在局部做比较。

多解法对比

解法时间空间适用场景
中序收集数组O(n)O(n)思路直观，但额外 O(n) 空间
递归上下界O(n)O(h)面试标准解，空间更优且可提前失败

为什么选递归上下界：它精准命中 BST 定义（子树整体受界约束），空间 O(h) 更优，而且能处理 int 边界值，是面试正解。

CodeTop 变体

#230 二叉搜索树中第 K 小的元素

题意

给定 BST 根节点和整数 k（从 1 计数），返回树中第 k 小的元素。

输入：root = [3,1,4,null,2], k = 1
输出：1

题目本质：BST 中序遍历即升序序列——第 k 次访问的节点就是答案，找到后立即停止。现实类比：翻字典找第 k 个词——按字母序（中序）翻到第 k 个词即停，不必翻完。

难点与易错点

解法一：中序收集全部（暴力 / 直观）

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        return values.get(k - 1);   // 中序升序，第 k 小下标 k-1
    }

    private void inorder(TreeNode node, List<Integer> values) {
        if (node == null) return;
        inorder(node.left, values);
        values.add(node.val);
        inorder(node.right, values);
    }
}

解法二：中序提前终止（最优 / 源材料主解）

class Solution {
    private int result;
    private int k;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return result;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;

        dfs(node.left);   // 先遍历左子树（值更小）

        // 每访问一个节点计数减 1，减到 0 即第 k 小
        if (--k == 0) {
            result = node.val;
            return;       // 找到后不再继续
        }

        if (k > 0) {      // 还未找到才递归右子树
            dfs(node.right);
        }
    }
}

复杂度逐步推导：中序遍历只需走到第 k 个节点即停止，访问的节点数 = 左子树沿路深度 + k，因此时间 = O(h + k)；最坏情况 k = n 时退化为 O(n)（仍需访问整棵树）。空间 = 递归栈深度 = O(h)，最坏 O(n)。对比解法一，节省了”第 k 个之后的 n−k 个节点”的遍历和 O(n) 数组。

进阶：若题目升级为”多次查询第 k 小”，提前在每个节点记录子树节点数（平衡 BST/AVL），每次查询可做到 O(log n)；173. 二叉搜索树迭代器也是同族技巧。

多解法对比

解法时间空间适用场景
中序收集O(n)O(n)直观，但冗余遍历 + 额外数组
提前终止O(h+k)O(h)面试标准解，找到即停

为什么选提前终止：题目只求第 k 小，无需遍历整棵树；提前终止在 k 较小时显著优于 O(n)。

CodeTop 变体

#199 二叉树的右视图

题意

给定二叉树根节点，返回从右侧看到的节点值（从上到下）。

输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

题目本质：BFS 层序遍历取每层最后一个节点。现实类比：站在楼梯右侧拍照——每层只拍最右边那根柱子，从上到下排列。

难点与易错点

解法一：BFS 层序取最后（直观 / 源材料主解）

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);

        while (!deque.isEmpty()) {
            int levelSize = deque.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = deque.poll();
                if (node.left  != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);

                // 每层最后一个节点即右视图可见节点
                if (i == levelSize - 1) {
                    result.add(node.val);
                }
            }
        }
        return result;
    }
}

解法二：DFS 根→右→左（优化）

先右后左递归，每层第一次访问到的节点就是最右节点。

class Solution {
    private List<Integer> result = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return result;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) return;

        // 每层第一次访问（根→右→左保证最右先到）即最右节点
        if (result.size() == depth) result.add(node.val);

        dfs(node.right, depth + 1);  // 先右
        dfs(node.left,  depth + 1);  // 后左
    }
}

复杂度逐步推导：DFS 每个节点访问一次，时间 = O(n)。空间 = 递归栈深度 = 树高 h → O(h)，最坏退化链表 O(n)；在”深而窄”的树上比 BFS 的 O(w) 更省。

多解法对比

解法时间空间适用场景
BFS 层序O(n)O(w)面试首选，直接复用 102 框架
DFS 根右左O(n)O(h)深窄树更省空间

为什么选 BFS：右视图是层序遍历的直接应用，i == levelSize - 1 一行就能取每层最后一个，与 102 题同框架，最好讲。

CodeTop 变体

#114 二叉树展开为链表

题意

给定二叉树根节点，将它原地展开为单链表：right 指针指向下一节点、left 始终为 null，展开顺序与前序遍历相同。

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

题目本质：后序递归——先把左右子树分别展成链表，再把左链表插到 root.right，原右子树拼到左链表末尾，root.left = null。现实类比：书目展平——先把左目录、右目录各自展成直线，再把左目录插到当前条目后，左目录末尾接右目录。

难点与易错点

解法一：先存前序再重建（暴力 / 直观）

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        List<TreeNode> nodes = new ArrayList<>();
        preorder(root, nodes);

        for (int i = 1; i < nodes.size(); i++) {
            TreeNode prev = nodes.get(i - 1);
            TreeNode cur  = nodes.get(i);
            prev.left  = null;
            prev.right = cur;
        }
        // 最后一个节点左右都置空
        TreeNode last = nodes.get(nodes.size() - 1);
        last.left  = null;
        last.right = null;
    }

    private void preorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        nodes.add(node);
        preorder(node.left, nodes);
        preorder(node.right, nodes);
    }
}

解法二：后序原地（优化；源材料写法）

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;

        // 后序：先展开右子树，再展开左子树
        flatten(root.right);
        flatten(root.left);

        // 保存展开后的左右链表头
        TreeNode leftList  = root.left;
        TreeNode rightList = root.right;

        // 将左链表移到 root.right，清空左指针
        root.left  = null;
        root.right = leftList;

        // 找到左链表末尾节点
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }

        // 末尾节点连接原右链表
        p.right = rightList;
    }
}

解法二·升级：返回尾节点，时间稳定 O(n)（真正最优）

把”找尾”从 while 扫描改为递归直接返回尾节点，一次定位 O(1)。

class Solution {
    public void flatten(TreeNode root) {
        flattenHelper(root);
    }

    // 展开以 node 为根的子树，返回展开后链表的尾节点
    private TreeNode flattenHelper(TreeNode node) {
        if (node == null) return null;

        TreeNode leftTail  = flattenHelper(node.left);   // 左子树展开后的尾
        TreeNode rightTail = flattenHelper(node.right);  // 右子树展开后的尾
        TreeNode rightHead = node.right;                 // 先保存右子树头

        if (node.left != null) {
            node.right      = node.left;  // 左链表接到右侧
            node.left       = null;
            leftTail.right  = rightHead;  // 左尾 O(1) 接右头
        }

        // 整棵子树链表的尾：优先右尾，其次左尾，否则自身
        if (rightTail != null) return rightTail;
        if (leftTail  != null) return leftTail;
        return node;
    }
}

复杂度逐步推导：每个节点恰好访问一次，且”找尾”通过返回值 O(1) 完成，不再有 while 重复扫描，因此总时间 = n · O(1) = O(n)。空间 = 递归栈深度 = 树高 h → O(h)，最坏退化链表 O(n)。若再追求极致，可用”迭代找前驱”（Morris 式）把空间压到 O(1)，面试提一嘴即可。

多解法对比

解法时间空间适用场景
先存前序再重建O(n)O(n)直观，但非原地
后序 while 找尾最坏 O(n²)O(h)常见写法，需警惕退化结构
后序返回尾节点O(n)O(h)面试最优解，时间稳定

为什么选返回尾节点版：既要”原地”（O(h) 空间），又要时间稳定 O(n)，它同时满足；while 找尾版在退化树上有 O(n²) 隐患，是面试官爱挖的坑。

CodeTop 变体

#105 从前序与中序遍历序列构造二叉树

题意

给定前序遍历 preorder 和中序遍历 inorder（无重复元素），构造并返回二叉树。

输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]

题目本质：递归分治——前序第一个元素是根，在中序中找到根的位置，即可划分左右子树长度，递归构建。现实类比：拼图还原——目录（前序）告诉你第一本书是什么，内容页（中序）告诉你这本书把书架分成左右两堆，左右两堆继续同样操作。

难点与易错点

解法一：线性查找根位置（暴力）

每次在中序里线性扫描根的位置，划分左右子树。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] pre, int[] in, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) return null;

        int rootVal = pre[preLeft];
        // 线性扫描中序找根位置：O(n)，每个节点都扫一次 → O(n^2)
        int inRoot = inLeft;
        while (in[inRoot] != rootVal) inRoot++;
        int leftSize = inRoot - inLeft;

        TreeNode root = new TreeNode(rootVal);
        root.left  = build(pre, in, preLeft + 1, preLeft + leftSize, inLeft, inRoot - 1);
        root.right = build(pre, in, preLeft + leftSize + 1, preRight, inRoot + 1, inRight);
        return root;
    }
}

解法二：HashMap 预处理（最优 / 源材料主解）

class Solution {
    private Map<Integer, Integer> inOrderIndex; // 中序元素 → 下标映射

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        inOrderIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            inOrderIndex.put(inorder[i], i);  // 预处理，O(1) 查根位置
        }
        return build(preorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode build(int[] preorder,
                           int preLeft, int preRight,
                           int inLeft,  int inRight) {
        if (preLeft > preRight) return null;

        int rootVal   = preorder[preLeft];           // 前序第一个是根
        int inRootIdx = inOrderIndex.get(rootVal);   // O(1) 查根在中序的位置
        int leftSize  = inRootIdx - inLeft;          // 左子树节点数

        TreeNode root = new TreeNode(rootVal);

        // 左子树：前序 [preLeft+1, preLeft+leftSize]，中序 [inLeft, inRootIdx-1]
        root.left  = build(preorder, preLeft + 1, preLeft + leftSize, inLeft, inRootIdx - 1);
        // 右子树：前序 [preLeft+leftSize+1, preRight]，中序 [inRootIdx+1, inRight]
        root.right = build(preorder, preLeft + leftSize + 1, preRight, inRootIdx + 1, inRight);

        return root;
    }
}

复杂度逐步推导：预处理建 HashMap 遍历 n 个元素 O(n)；递归阶段每个节点恰好被创建一次，且查根位置从 O(n) 降到 O(1)，总时间 = O(n) 建表 + n · O(1) 建树 = O(n)。空间 = HashMap 存 n 个映射 O(n) + 递归栈 O(h)（最坏 O(n)）→ O(n)。

多解法对比

解法时间空间适用场景
线性查找根O(n²)O(h)仅作思路铺垫
HashMap 预处理O(n)O(n)面试标准解

为什么选 HashMap：n 可达 10⁴，O(n²) 会超时；用空间换时间，把定位根的开销从 O(n) 降到 O(1)，整体降为 O(n)。

CodeTop 变体

#437 路径总和 III

题意

给定二叉树根节点和整数 targetSum，求路径和等于 targetSum 的路径数目。路径不要求从根开始、也不要求在叶子结束，但方向必须向下（从祖先到后代）。

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3

题目本质：前缀和 + DFS 回溯（同 560 题思路）——用 map 记录根到当前节点路径上每个前缀和的出现次数，查 currentSum - targetSum 的个数即得路径数，回溯时撤销。现实类比：营业额统计——从总店（根）到分店（当前节点）的累计营业额是前缀和，找某段路径正好符合目标营业额，提前建好”账本”（map）快速查询。

难点与易错点

解法一：双重递归（暴力 / 直观）

对每个节点都作为起点，向下统计路径和，再递归左右子树。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        // 以 root 为起点的路径数 + 左右子树各自内部的路径数
        return pathFrom(root, targetSum)
             + pathSum(root.left, targetSum)
             + pathSum(root.right, targetSum);
    }

    // 以 node 为起点向下延伸、和等于 sum 的路径条数
    private int pathFrom(TreeNode node, long sum) {
        if (node == null) return 0;
        int count = 0;
        if (node.val == sum) count++;
        count += pathFrom(node.left,  sum - node.val);
        count += pathFrom(node.right, sum - node.val);
        return count;
    }
}

解法二：前缀和 + 回溯（最优 / 源材料主解）

class Solution {
    private int answer = 0;

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixCount = new HashMap<>();
        // 前缀和为 0 出现 1 次，处理从根开始的路径
        prefixCount.put(0L, 1);
        dfs(root, 0L, targetSum, prefixCount);
        return answer;
    }

    private void dfs(TreeNode node, long currentSum, int targetSum,
                     Map<Long, Integer> prefixCount) {
        if (node == null) return;

        currentSum += node.val;

        // 存在前缀 currentSum - targetSum，则它到当前节点的路径和 = targetSum
        answer += prefixCount.getOrDefault(currentSum - targetSum, 0);

        // 将当前前缀和加入计数（merge 简化 Java 8 写法）
        prefixCount.merge(currentSum, 1, Integer::sum);

        dfs(node.left,  currentSum, targetSum, prefixCount);
        dfs(node.right, currentSum, targetSum, prefixCount);

        // 回溯：离开当前节点时撤销前缀和记录，避免影响其他分支
        prefixCount.merge(currentSum, -1, Integer::sum);
    }
}

复杂度逐步推导：每个节点恰好访问一次，每次做 O(1) 的 HashMap 查询和两次 merge，总时间 = n · O(1) = O(n)（对比双重递归的 O(n²)，省掉了”每个起点重复扫描”的 n 倍开销）。空间 = 前缀和 map（最坏存 n 个不同前缀和）O(n) + 递归栈 O(h) → O(n)。

💭 思考：为什么「任意祖先到当前节点」的区间和能用前缀和相减 O(1) 求？——路径只能向下走，所以任何合法路径都是一段「从某个祖先到当前节点」的连续链，路径和 = currentSum - 祖先处的前缀和。要找和等于 targetSum 的路径，就等价于「当前前缀和 currentSum 时，前面是否出现过 currentSum - targetSum」。于是用 map 记录路径上每个前缀和的次数，走到哪查到哪，回溯时 merge(currentSum, -1) 撤销。这个信号就是「路径必须向下 + 求区间和」——看到这两个条件组合，就该从「每个节点都当起点扫一遍」（双重递归 O(n²)）升级成「前缀和 + map」的一次遍历。

多解法对比

解法时间空间适用场景
双重递归O(n²)O(h)直观但会超时
前缀和 + 回溯O(n)O(n)面试标准解，一次遍历

为什么选前缀和：n 可达 10³~10⁴ 且节点值可正可负（不能靠剪枝），必须用前缀和把”任意祖先到当前节点”的区间和查询降到 O(1)。

CodeTop 变体

#236 二叉树的最近公共祖先

题意

给定二叉树和两个节点 p、q，返回它们的最近公共祖先（LCA）——深度最大且同时是二者祖先的节点（节点可以是自己的祖先）。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

题目本质：后序递归分情况——左右子树都找到则当前节点是 LCA；只有一侧找到就返回那一侧；都没找到返回 null。现实类比：家谱查共同祖先——分别往左右两支找目标人，两支都找到则当前节点就是最近公共祖先，只有一支找到就是那支的结果。

难点与易错点

解法一：记录父节点（暴力 / 直观）

先遍历建父指针表，收集 p 的祖先集合，再让 q 向上跳找第一个公共祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        parent.put(root, null);
        stack.push(root);

        // 遍历直到 p 和 q 的父指针都记录完毕
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left  != null) { parent.put(node.left,  node); stack.push(node.left);  }
            if (node.right != null) { parent.put(node.right, node); stack.push(node.right); }
        }

        // 收集 p 的所有祖先
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) { ancestors.add(p); p = parent.get(p); }

        // q 向上跳，找到第一个出现在 p 祖先集合中的节点
        while (!ancestors.contains(q)) { q = parent.get(q); }
        return q;
    }
}

解法二：后序递归（最优 / 源材料主解）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }

    private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q) {
        // 递归出口：遇到 null、p 或 q 就返回（找到即停）
        if (node == null || node == p || node == q) return node;

        TreeNode leftResult  = dfs(node.left, p, q);
        TreeNode rightResult = dfs(node.right, p, q);

        // 左右都找到：当前节点是 LCA
        if (leftResult != null && rightResult != null) return node;
        // 只有左边找到：LCA 在左子树中
        if (leftResult != null) return leftResult;
        // 只有右边找到（或都没找到返回 null）
        return rightResult;
    }
}

复杂度逐步推导：后序遍历每个节点访问一次，每节点 O(1) 判断，时间 = n · O(1) = O(n)。空间 = 递归栈深度 = 树高 h → O(h)，最坏退化链表 O(n)。对比解法一，省掉了 O(n) 的父指针表和祖先集合，空间从 O(n) 降到 O(h)。

多解法对比

解法时间空间适用场景
记录父节点O(n)O(n)思路直观，但空间开销大
后序递归O(n)O(h)面试标准解，空间更优

为什么选后序递归：LCA 的定义天然是”自底向上汇聚”，后序递归把结果一路回传，既 O(n) 时间又 O(h) 空间，是本题最优雅的正解。

CodeTop 变体

#124 二叉树中的最大路径和

题意

路径是节点序列，相邻节点有边相连，同一节点至多出现一次，至少包含一个节点，且不一定经过根节点。返回最大路径和。

输入：root = [1,2,3]
输出：6   （路径 2 → 1 → 3）

题目本质：DFS 后序算”单边最大贡献” + 全局更新——每个节点返回”可向上贡献的最大单侧路径和”（负则返回 0），同时用左贡献 + 右贡献 + 自身更新全局最大路径和。现实类比：最高收益旅行路线——每个城市统计”通过我的最长收益路线 = 左边最优 + 右边最优 + 我自己”，同时告诉上级”我这一侧能给你的最大收益”。

难点与易错点

解法一：朴素双重计算（暴力）

对每个节点，都重新调用一次 maxDown 求左右单侧最大和来更新答案，深度信息反复计算。

class Solution {
    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        // 以 root 为最高点的最大路径 = 左单侧 + 右单侧 + 自身
        int throughRoot = maxDown(root.left) + maxDown(root.right) + root.val;
        ans = Math.max(ans, throughRoot);
        // 左右子树内部的答案（重复遍历，O(n^2)）
        maxPathSum(root.left);
        maxPathSum(root.right);
        return ans;
    }

    // 以 node 为起点的单侧最大路径和（负则取 0 表示不走）
    private int maxDown(TreeNode node) {
        if (node == null) return 0;
        return Math.max(0, Math.max(maxDown(node.left), maxDown(node.right)) + node.val);
    }
}

解法二：后序一次遍历（最优 / 源材料主解）

class Solution {
    private int maxPathSum = Integer.MIN_VALUE; // 结果可能为负，初始为最小 int

    public int maxPathSum(TreeNode root) {
        maxContribution(root);
        return maxPathSum;
    }

    // 返回以 root 为起点、向下延伸的最大路径和（可贡献给父节点的值）
    private int maxContribution(TreeNode node) {
        if (node == null) return 0;

        // 左右子树的最大贡献值（若为负则舍弃，贡献视为 0）
        int leftVal  = Math.max(maxContribution(node.left),  0);
        int rightVal = Math.max(maxContribution(node.right), 0);

        // 经过当前节点的完整路径：左贡献 + 节点值 + 右贡献
        maxPathSum = Math.max(maxPathSum, leftVal + rightVal + node.val);

        // 向父节点返回单侧最大贡献（只能选左或右，不能同时选）
        return Math.max(leftVal, rightVal) + node.val;
    }
}

复杂度逐步推导：一次后序遍历，每个节点访问一次，每个节点内做常数次 Math.max，总时间 = n · O(1) = O(n)（对比暴力版，把 n 次 O(n) 的 maxDown 合并进同一次遍历）。空间 = 递归栈深度 = 树高 h → O(h)，最坏退化链表 O(n)。

💭 思考：这题和 #543 直径是同一套模板，多出来的「负值取 0」为什么必不可少？——路径和允许为负，负的子树贡献会拉低答案，所以返回给父节点的单侧贡献要 Math.max(贡献, 0)，负数就「不走这一侧」；但全局答案的初值必须是 Integer.MIN_VALUE，因为整条路径可能全为负。想通「返回值（单侧、可舍弃负值）vs 全局答案（完整拐点、可为负）」这层差别，就知道为什么同样的后序模板在这里要多加一句 Math.max(..., 0)——这正是从 543 到 124 的题眼，也是面试官最爱追问的点。

多解法对比

解法时间空间适用场景
朴素双重计算O(n²)O(h)仅作思路铺垫
后序一次遍历O(n)O(h)面试标准解

为什么选后序一次遍历：这是”树形 DP / 后序聚合”的巅峰题，与 543 直径同一模板（把”深度”换”路径和”、多加”负值取 0”），一次遍历即可在 O(n) 内求最优。

CodeTop 变体

总结：15 题的两条主线

  1. 遍历线（94 中序、102 层序、199 右视图、230 第 K 小、98 验证 BST）：掌握”前/中/后序只是 add 位置不同”和”层序靠 levelSize 快照分层”，这 5 题就是模板的排列组合。
  2. 后序自底向上线（104 深度、226 翻转、101 对称、543 直径、114 展开、236 LCA、124 最大路径和）：套路是”递归返回值 = 单侧贡献 + 全局变量更新答案”，543 与 124 是这套模板的一对巅峰姊妹题。
  3. 分治构造/前缀和线（108 有序数组转 BST、105 前中序构造、437 路径和 III）：抓住”中点/根位置划分”和”前缀和回溯”两个关键动作。

手撕时先判断题目属于哪条主线，套对应模板，再针对题目的坑（负值、边界、镜像位置、提前终止）微调，15 题即可无痛拿下。

章末提问

二叉树篇的追问多集中在「为什么选这个解法 / 复杂度怎么推 / 边界怎么抠」这类思考型问题。下面是最常考的 5 个角度（结论先行，因为跟着原因）：

  1. 「二叉树遍历，递归和迭代分别什么时候用？」 回答思路：结论是默认递归（代码最短、最不易错），只有树可能退化到极深会栈溢出、或需要「暂停 / 恢复」遍历（如 173 迭代器）时才上显式栈迭代，因为递归本质是系统调用栈，其深度等于树高，最坏退化链表时是 O(n)。

  2. 「543 直径和 124 最大路径和，为什么一次后序就能做到 O(n)？」 回答思路：结论是让递归「返回单侧贡献 + 全局变量更新答案」，把每个节点的左右深度 / 贡献合并进同一次遍历，因为暴力版对每个节点都重复求子树深度导致 O(n²)，后序复用返回值就省掉了 n 倍的重复计算。

  3. 「从 O(n²) 优化到 O(n)，你在这篇里用了哪几种手段？」 回答思路：结论是三种——复用返回值（543/124）、HashMap 预处理换时间（105 建表 O(1) 查根位置）、前缀和把区间查询降到 O(1)（437），因为它们共同的病灶都是「重复扫描 / 重复计算」，用空间或返回值缓存即可一次遍历完成。

  4. 「验证 BST 为什么不能只比较当前节点和左右孩子，必须传上下界？」 回答思路：结论是 BST 要求「整棵子树」所有值都落在界内，只看直接子节点会漏掉跨层违规（如 [5,1,4,null,null,3,6] 中 3 在右子树却小于根），因为右子树所有节点都要大于根，必须把界向下逐层收紧传递。

  5. 「边界细节：为什么 BST 上下界用 long，直径和最大路径和却用全局变量？」 回答思路：结论是节点值可能是 Integer.MIN_VALUE / MAX_VALUE，用 int 边界会与「严格小于 / 大于」冲突所以要 long；而直径和最大路径和可以不经过根、必须每个节点都更新答案，所以用全局变量，因为只算根节点的左右拼接会漏掉子树的更优解。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——图论篇（DFS、BFS、拓扑排序、Trie）
Next Post
字母异位词分组——HashMap处理集合分组的经典模式