Java二叉树面试题 —— 系统化突破技术关卡
一、二叉树在Java面试中的战略地位
为何二叉树是Java工程师的必考项?
二叉树作为**树结构**中最基础、最经典的模型,因其递归定义、清晰的层次关系与丰富的操作变体,成为技术面试中考察算法思维与编码能力的黄金载体。在**阿里、腾讯、字节、拼多多、美团**等一线大厂的后端、大数据、基础架构岗中,二叉树题目出现率高达85%以上,且多以中高难度题型(如路径和、最近公共祖先、树的重建)为主。
考察本质在于:是否具备递归建模能力、DFS/BFS思维迁移能力、空间换时间优化意识,以及边界条件处理的严谨性。尤其在LeetCode热题100中,树相关题目占比近1/3,其中二叉树的最大深度、验证二叉搜索树、从中序与后序遍历构造二叉树等均为高频考点。
需注意:Java开发者常因语言特性忽略性能细节——如递归深度导致的栈溢出(StackOverflowError)、频繁创建对象引发的GC压力、未考虑空指针异常等,这恰恰是面试官关注的工程素养维度。
二叉树知识体系全景图
构建系统认知框架是高效备考的前提。下图展示Java二叉树面试的知识脉络,以**二叉树基础 → 遍历 → 特殊树型 → 高频算法 → 工程实践**为逻辑主线:
- 基础概念:节点、度、高度、深度、叶子节点、满二叉树、完全二叉树、二叉搜索树(BST)、平衡二叉树(AVL)、红黑树
- 存储结构:链式存储(Java常用)、顺序存储(数组实现堆)、线索化二叉树
- 核心操作:创建、插入、删除、查找、遍历(先序/中序/后序/层序)
- 算法维度:递归解法、迭代解法、Morris遍历、回溯、动态规划、分治思想
- 扩展应用:树的序列化与反序列化、树的直径、LCA(最近公共祖先)、树同构判定
尤其需掌握:**二叉搜索树的中序遍历有序性**、**AVL旋转平衡机制**、**红黑树五条性质**——这些不仅是理论考点,更是HashMap、TreeMap底层设计的核心依据。
二、二叉树核心概念与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核心操作:插入保持有序性,删除分三种情况:
- 无子节点:直接删除
- 单子节点:用子节点替代
- 双子节点:用右子树最小值(中序后继)或左子树最大值(中序前驱)替代
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层)时可能溢出。规避方案:
- 改用迭代(显式栈)
- 使用Tail Recursion Optimization(Java不支持,需语言级支持)
- 对极端退化树(链表)使用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(持续):模拟面试实战,重点训练代码鲁棒性(空指针、整数溢出、边界条件)
终极技巧:画图!手动画树结构比纯脑补更高效,面试时可画在白板上辅助思考