Java二叉树面试题 —— 系统化突破技术关卡

一、二叉树在Java面试中的战略地位

为何二叉树是Java工程师的必考项?

二叉树作为**树结构**中最基础、最经典的模型,因其递归定义、清晰的层次关系与丰富的操作变体,成为技术面试中考察算法思维与编码能力的黄金载体。在**阿里、腾讯、字节、拼多多、美团**等一线大厂的后端、大数据、基础架构岗中,二叉树题目出现率高达85%以上,且多以中高难度题型(如路径和、最近公共祖先、树的重建)为主。

考察本质在于:是否具备递归建模能力、DFS/BFS思维迁移能力、空间换时间优化意识,以及边界条件处理的严谨性。尤其在LeetCode热题100中,树相关题目占比近1/3,其中二叉树的最大深度、验证二叉搜索树、从中序与后序遍历构造二叉树等均为高频考点。

需注意:Java开发者常因语言特性忽略性能细节——如递归深度导致的栈溢出(StackOverflowError)、频繁创建对象引发的GC压力、未考虑空指针异常等,这恰恰是面试官关注的工程素养维度。

二叉树知识体系全景图

构建系统认知框架是高效备考的前提。下图展示Java二叉树面试的知识脉络,以**二叉树基础 → 遍历 → 特殊树型 → 高频算法 → 工程实践**为逻辑主线:

  • 基础概念:节点、度、高度、深度、叶子节点、满二叉树、完全二叉树、二叉搜索树(BST)、平衡二叉树(AVL)、红黑树
  • 存储结构:链式存储(Java常用)、顺序存储(数组实现堆)、线索化二叉树
  • 核心操作:创建、插入、删除、查找、遍历(先序/中序/后序/层序)
  • 算法维度:递归解法、迭代解法、Morris遍历、回溯、动态规划、分治思想
  • 扩展应用:树的序列化与反序列化、树的直径、LCA(最近公共祖先)、树同构判定

尤其需掌握:**二叉搜索树的中序遍历有序性**、**AVL旋转平衡机制**、**红黑树五条性质**——这些不仅是理论考点,更是HashMap、TreeMap底层设计的核心依据。

二、二叉树核心概念与Java实现精要

基础节点定义与常见陷阱

标准二叉树节点定义如下:

TreeNode.java
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;
    }
}

需警惕的细节:

  • 空指针风险:左/右子树为null时未判空,导致NPE
  • 值域范围:节点值可能为负(如LeetCode #124),不可用val == 0判断空节点
  • 递归终止条件:应判断node == null而非node.left == null && node.right == null(后者仅适用于叶子节点场景)

递归 vs 迭代:思维范式对比

以**先序遍历**为例:

public List preorderTraversal(TreeNode root) {
    List res = new ArrayList<>();
    helper(root, res);
    return res;
}
private void helper(TreeNode node, List res) {
    if (node == null) return;
    res.add(node.val);       // 访问根
    helper(node.left, res);  // 遍历左子树
    helper(node.right, res); // 遍历右子树
}

优势:代码简洁,贴近数学递归定义,易理解;劣势:深度过大时栈溢出,Java默认栈深度约1000层(可通过-Xss调整,但不可靠)

public List preorderTraversal(TreeNode root) {
    List res = new ArrayList<>();
    if (root == null) return res;
    Deque stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);     // 根
        if (node.right != null) stack.push(node.right); // 先压右!
        if (node.left != null)  stack.push(node.left);
    }
    return res;
}

关键点:栈模拟递归调用栈;先压右子树再压左子树(保证左子树先出栈);避免使用stack.push(node.left); stack.push(node.right);顺序错误导致遍历反序

Morris遍历:O(1)空间复杂度的突破

中序Morris遍历核心思想:利用叶子节点的空右指针指向中序后继节点,实现无栈遍历。

public List inorderMorris(TreeNode root) {
    List res = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            res.add(cur.val);   // 无左子树,直接访问
            cur = cur.right;
        } else {
            TreeNode pre = cur.left;
            // 找到左子树的最右节点(中序前驱)
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = cur; // 建立线索
                cur = cur.left;
            } else {
                pre.right = null; // 恢复树结构
                res.add(cur.val); // 访问节点
                cur = cur.right;
            }
        }
    }
    return res;
}

优势:空间复杂度O(1);代价:修改树结构(遍历后需恢复),代码复杂度高,面试中慎用(除非明确要求空间最优)

三、四大遍历方式深度解析与高频变体

层序遍历(BFS)的灵活应用

层序遍历是解决树的层级问题(如层高、每层最值、Z字形遍历)的核心工具。标准实现需用队列:

public List> levelOrder(TreeNode root) {
    List> res = new ArrayList<>();
    if (root == null) return res;
    Queue queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

变体场景:

  • Z字形遍历:用boolean leftToRight控制每层是否反转level列表
  • 每层节点数:直接取size即当前层节点数
  • 右视图:每层最后一个节点即视图节点

中序遍历的特殊价值:二叉搜索树的有序性

对二叉搜索树(BST)进行中序遍历,结果必为递增序列!这是解题的关键突破口:

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode node, long lower, long upper) {
    if (node == null) return true;
    if (node.val <= lower || node.val >= upper) return false;
    return helper(node.left, lower, node.val) &&
           helper(node.right, node.val, upper);
}

原理:每个节点值必须严格大于左子树所有值、小于右子树所有值

// 中序遍历中序遍历第k个节点即为第k小
int count = 0, res = 0;
public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return res;
}
private void inorder(TreeNode node, int k) {
    if (node == null || count >= k) return;
    inorder(node.left, k);
    count++;
    if (count == k) res = node.val;
    inorder(node.right, k);
}

优化:可记录左子树节点数,实现O(log n)时间复杂度(需增强树节点存储子树大小)

后序遍历:自底向上构建解

后序遍历(左右根)适合解决子树问题,如:

  • 二叉树最大深度:左右子树深度+1
  • 二叉树直径:通过全局变量记录经过当前节点的最长路径(左深度+右深度)
  • 路径和问题:从根到叶子节点路径和是否等于目标值

经典题型:求二叉树直径(LeetCode #543):

int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return maxDiameter;
}
private int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left);
    int right = depth(node.right);
    maxDiameter = Math.max(maxDiameter, left + right); // 累计左右深度
    return Math.max(left, right) + 1;
}

四、特殊树型结构:从理论到工程落地

二叉搜索树(BST)的插入与删除

BST核心操作:插入保持有序性,删除分三种情况:

  1. 无子节点:直接删除
  2. 单子节点:用子节点替代
  3. 双子节点:用右子树最小值(中序后继)或左子树最大值(中序前驱)替代
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else { // 找到节点
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 双子节点:找右子树最小值
        TreeNode min = findMin(root.right);
        root.val = min.val;
        root.right = deleteNode(root.right, min.val);
    }
    return root;
}
private TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

工程意义:TreeMap底层红黑树的删除逻辑比BST复杂(需维持平衡),但核心思想一致

平衡二叉树(AVL)与红黑树:面试高频对比

特性AVL树红黑树Java应用
平衡条件左右子树高度差≤1任一节点:左子树黑高=右子树黑高;无连续红节点TreeMap/TreeSet
旋转次数插入/删除可能多次旋转插入最多2次旋转;删除最多3次高频插入场景更优
查询效率严格O(log n),常数小O(log n),常数略大查询密集场景AVL更优
Java实现无原生实现HashMap节点、TreeMap底层HashMap链表转红黑树阈值=8

关键点:红黑树的“黑高”概念是理解其平衡性的核心——从任一节点到其叶子节点的所有路径上,黑节点数量相同

完全二叉树与堆:数组存储的威力

完全二叉树可用数组高效存储(索引关系:父= (i-1)/2;左=2i+1;右=2i+2),是堆(Heap)的基础。

堆的典型应用:

  • 优先队列:Java的PriorityQueue底层是小顶堆
  • Top K问题:用大小为k的小顶堆,时间O(n log k)
  • 合并K个有序链表:用堆维护每链表当前最小节点
// 构建小顶堆(PriorityQueue默认为小顶)
PriorityQueue minHeap = new PriorityQueue<>();
// 添加元素自动调整堆结构
minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
// 取出最小值:1 → 3 → 5

五、网民最关注的10大热点问题深度解析

问题1:如何快速判断两棵树是否相同?

递归解法:结构相同且节点值相等。

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return p.val == q.val &&
           isSameTree(p.left, q.left) &&
           isSameTree(p.right, q.right);
}

扩展:若允许节点值顺序不同但结构相同(如对称树),需比较isSameTree(p.left, q.right) && isSameTree(p.right, q.left)

问题2:二叉树的最近公共祖先(LCA)

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; // p/q在两侧
    return left != null ? left : right; // 同侧
}

关键点:后序遍历自底向上;返回值含义:以当前节点为根的子树中找到的最近公共祖先

public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val)
        return lowestCommonAncestorBST(root.left, p, q);
    if (p.val > root.val && q.val > root.val)
        return lowestCommonAncestorBST(root.right, p, q);
    return root; // 分叉点即LCA
}

效率优势:利用BST有序性,时间O(h)(h为树高),比普通解法快2倍以上

问题3:路径和问题全家福

路径定义:从任意节点出发到任意节点的向下路径(可不经过根)。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null)
        return targetSum == root.val;
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

变体:返回所有路径(需回溯)

int count = 0;
Map prefix = new HashMap<>();
public int pathSum(TreeNode root, int targetSum) {
    prefix.put(0L, 1); // 前缀和为0出现1次
    dfs(root, 0, targetSum);
    return count;
}
private void dfs(TreeNode node, long currSum, int target) {
    if (node == null) return;
    currSum += node.val;
    count += prefix.getOrDefault(currSum - target, 0);
    prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1);
    dfs(node.left, currSum, target);
    dfs(node.right, currSum, target);
    // 回溯:移除当前节点影响
    prefix.put(currSum, prefix.get(currSum) - 1);
}

核心思想:前缀和 + 哈希表优化;时间O(n),空间O(n)

问题4:树的序列化与反序列化

常用方案:前序+空节点标记(如"#")。

// 序列化
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeHelper(root, sb);
    return sb.toString();
}
private void serializeHelper(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("#,");
        return;
    }
    sb.append(node.val).append(",");
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}
// 反序列化
public TreeNode deserialize(String data) {
    String[] arr = data.split(",");
    Queue queue = new LinkedList<>(Arrays.asList(arr));
    return deserializeHelper(queue);
}
private TreeNode deserializeHelper(Queue queue) {
    String val = queue.poll();
    if ("#".equals(val)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserializeHelper(queue);
    node.right = deserializeHelper(queue);
    return node;
}

工程应用:持久化存储树结构、网络传输树对象

问题5:验证二叉搜索树的5种解法对比

方法时间空间适用场景
递归边界O(n)O(n)通用
中序遍历O(n)O(n)BST特有
Morris中序O(n)O(1)空间敏感
迭代中序O(n)O(n)防栈溢出
分治(返回范围)O(n)O(n)可扩展性高

问题6:树的直径计算误区

常见错误:直径=左子树高度+右子树高度(仅适用于经过根节点的路径)。

正确解法:在递归中动态更新全局最大值(如前文所述),因直径可能完全位于子树内。

反例:左子树为深度10的链表,右子树为空 → 直径=10,但根的左右高度和=10+0=10(巧合相等);若左子树深度5、右子树深度8,但左子树内部有深度12的路径 → 直径=12 ≠ 5+8

问题7:对称二叉树的高效验证

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

迭代解法:用队列成对入队左右子树节点,成对出队比较

问题8:重建二叉树:输入前序+中序,输出树结构

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map inMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inMap.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
}
private TreeNode build(int[] pre, int preL, int preR,
                       int[] in, int inL, int inR,
                       Map inMap) {
    if (preL > preR || inL > inR) return null;
    int rootVal = pre[preL];
    int rootIdx = inMap.get(rootVal);
    int leftSize = rootIdx - inL;
    TreeNode root = new TreeNode(rootVal);
    root.left = build(pre, preL + 1, preL + leftSize, in, inL, rootIdx - 1, inMap);
    root.right = build(pre, preL + leftSize + 1, preR, in, rootIdx + 1, inR, inMap);
    return root;
}

关键优化:哈希表存储中序遍历值-索引映射,避免每次O(n)查找

问题9:二叉树转链表(原地展开)

要求:将二叉树展开为单链表,右子指针指向下一个节点,左子指针为null。

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

思路:反向后序遍历(右→左→根),用prev记录前驱节点

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

原理:将右子树接到左子树最右节点,再将左子树移到右侧

问题10:树的子结构判断

题意:判断tree2是否为tree1的子结构(节点值相等且结构相同,注意子结构不要求是子树)。

public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null) return false;
    return isSame(A, B) ||
           isSubStructure(A.left, B) ||
           isSubStructure(A.right, B);
}
private boolean isSame(TreeNode a, TreeNode b) {
    if (b == null) return true; // B遍历完
    if (a == null || a.val != b.val) return false;
    return isSame(a.left, b.left) && isSame(a.right, b.right);
}

易错点:空树不是任意树的子结构(题目隐含条件)

六、高频真题精讲:LeetCode 10题实战拆解

题1:二叉树的最大深度(#104)

递归解法:深度=max(左子树深度, 右子树深度)+1

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

迭代解法:层序遍历统计层数

题2:平衡二叉树(#110)

解法1:自顶向下(重复计算,O(n²))

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int left = height(root.left);
    int right = height(root.right);
    return Math.abs(left - right) <= 1 &&
           isBalanced(root.left) && isBalanced(root.right);
}
private int height(TreeNode node) {
    if (node == null) return 0;
    return Math.max(height(node.left), height(node.right)) + 1;
}

解法2(推荐):自底向上,边计算高度边判断平衡性

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
private int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);
    if (left == -1) return -1;
    int right = height(node.right);
    if (right == -1 || Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

题3:二叉树的最小深度(#111)

注意:最小深度是从根到最近叶子节点的节点数(非到叶子的路径长度)。

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    if (root.left == null) return minDepth(root.right) + 1;
    if (root.right == null) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

题4:路径总和III(#437)

见前文“问题3”的前缀和解法,此处强调空间优化:递归回溯时需移除当前节点的前缀和计数,避免影响兄弟子树。

题5:二叉搜索树中第K小的元素(#230)

利用BST中序遍历有序性,记录访问序号。

int count = 0, res = 0;
public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return res;
}
private void inorder(TreeNode node, int k) {
    if (node == null || count >= k) return;
    inorder(node.left, k);
    count++;
    if (count == k) res = node.val;
    inorder(node.right, k);
}

题6:二叉树的右视图(#199)

层序遍历每层最后一个节点。

public List rightSideView(TreeNode root) {
    List res = new ArrayList<>();
    if (root == null) return res;
    Queue queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (i == size - 1) res.add(node.val); // 最后一个
            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return res;
}

题7:对称二叉树(#101)

见前文“问题7”的递归解法

题8:从中序与后序遍历构造二叉树(#106)

后序遍历最后一个元素是根节点,据此划分中序序列。

public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map inMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
    return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inMap);
}
private TreeNode build(int[] in, int inL, int inR,
                       int[] post, int postL, int postR,
                       Map inMap) {
    if (inL > inR || postL > postR) return null;
    int rootVal = post[postR];
    int rootIdx = inMap.get(rootVal);
    int leftSize = rootIdx - inL;
    TreeNode root = new TreeNode(rootVal);
    root.left = build(in, inL, rootIdx - 1, post, postL, postL + leftSize - 1, inMap);
    root.right = build(in, rootIdx + 1, inR, post, postL + leftSize, postR - 1, inMap);
    return root;
}

题9:二叉树的层序遍历II(#107)

标准层序遍历 + 最后反转结果列表。

public List> levelOrderBottom(TreeNode root) {
    List> res = new ArrayList<>();
    if (root == null) return res;
    Queue queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    Collections.reverse(res);
    return res;
}

题10:二叉搜索树的最近公共祖先(#235)

见前文“问题2”的BST特例解法

八、高频问答:面试官常问的10个灵魂拷问

Q1:为什么红黑树比AVL树更常用?

A:红黑树牺牲少量查询性能(因平衡性略弱),换取插入/删除时更少的旋转次数。在工程实践中,写操作(插入/删除)远多于纯查询,红黑树的综合性能更优。Java集合框架(如TreeMap)选择红黑树正是基于此权衡。

Q2:递归解法何时会栈溢出?如何规避?

A:当树深度 > JVM栈深度(默认约1000层)时可能溢出。规避方案:

  1. 改用迭代(显式栈)
  2. 使用Tail Recursion Optimization(Java不支持,需语言级支持)
  3. 对极端退化树(链表)使用Morris遍历

Q3:如何判断一棵树是完全二叉树?

A:层序遍历中,一旦遇到空节点,则后续所有节点必须为空。否则不是完全二叉树。

public boolean isCompleteTree(TreeNode root) {
    if (root == null) return true;
    Queue queue = new LinkedList<>();
    queue.offer(root);
    boolean encounteredNull = false;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            encounteredNull = true;
        } else {
            if (encounteredNull) return false;
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    return true;
}

Q4:Morris遍历如何保证不丢失信息?

A:Morris遍历利用叶子节点的空指针建立线索(临时指针),遍历后立即恢复原结构。核心在于:线索的建立与拆除严格对称,确保树结构不变。

Q5:二叉搜索树删除节点时,为什么选右子树最小值?

A:选右子树最小值(中序后继)或左子树最大值(中序前驱)均可,但需保持BST有序性。右子树最小值是大于当前节点的最小值,替换后仍满足左<根<右的性质。

Q6:如何设计支持O(1)时间获取最小值的栈?

A:用辅助栈存储当前最小值。但若要求支持树结构的最小值查询,需用线段树或稀疏表(ST表)预处理,时间O(n log n)建表,O(1)查询。

Q7:树的子结构 vs 子树的区别?

A:

  • 子树:必须是某个节点及其所有后代(如以节点A为根的整棵子树)
  • 子结构:只需匹配部分结构(如只匹配左子树的局部)

子树必是子结构,但子结构不一定是子树。

Q8:前序+后序遍历能否唯一确定一棵树?

A:不能!因无法区分左右子树。例如:根→左→右 与 根→右→左 的前序+后序序列相同(仅当树为满二叉树时可部分还原)。

Q9:如何验证一棵树是否为二叉搜索树?

A:最可靠方法是递归检查每个节点值是否在合法区间(min, max)内,而非仅比较左右子节点。中序遍历检查有序性也正确,但需注意严格递增(不可相等)。

Q10:树的序列化方案有哪些?优劣对比?

方案优点缺点
前序+空标记简单直观,易实现空间略大(每个空节点占位)
后序+空标记适合反序列化构建同上
层序+空标记直观展示树结构需处理大量空节点
仅存非空节点空间最优需额外存储索引关系

备考建议:分阶段突破策略

阶段1(1周):掌握基础概念与四大遍历,刷LeetCode树专题前20题(简单+中等)

阶段2(2周):精研BST/AVL/红黑树原理,攻克路径和、LCA、重建树等高频题

阶段3(持续):模拟面试实战,重点训练代码鲁棒性(空指针、整数溢出、边界条件)

终极技巧:画图!手动画树结构比纯脑补更高效,面试时可画在白板上辅助思考