说实话，第一次看到“二叉树”这三个字的时候，我的脑回路就像被打了个结。明明以前学数据结构的时候觉得挺简单的，可一遇到LeetCode上的题，尤其是那些需要递归回溯的硬骨头，我就开始怀疑人生了。但自从跟着李教授的课程，把力扣热题100道里的重点啃下来之后，我才真正明白：算法不是靠背的，是靠“悟”的。今天我就想跟你聊聊，我是怎么从一个连前序遍历都搞混的小白，一步步变成能从容应对面试中“动态规划”和“二叉树”高频考点的。
一、为什么是“二叉树”？因为它长得像个家谱
很多人学算法喜欢从数组、链表开始，这没错。但如果你想去大厂面试，二叉树是绕不过去的一道坎。为什么？因为它最能考察一个人的递归思维。
李教授在课上说了一句让我印象特别深的话：“二叉树就像你家的族谱，你顺着血缘往下找，那就是遍历；你从下往上整理关系，那就是构造。”这句话一下子把我打通了。
1.1 遍历的三种姿势：前、中、后
别急着背代码，先理解它的物理意义。
想象你在参观一个博物馆，展品是挂在树上的节点。
- 前序遍历（Pre-order）：先拍照（访问根节点），再逛左边展厅（左子树），最后逛右边展厅（右子树）。
- 中序遍历（In-order）：先逛左边展厅（左子树），再拍照（访问根节点），最后逛右边展厅（右子树）。
- 后序遍历（Post-order）：先逛左边展厅（左子树），再逛右边展厅（右子树），最后拍照（访问根节点）。
你看，是不是像不像你收拾房间？
- 前序：先把桌子上的东西收起来（根），再收左边抽屉，再收右边抽屉。
- 后序：先把左边抽屉清了，再清右边抽屉，最后才能把桌子清空。
在Java里，这种递归写法简洁得让人想哭：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTreeTraversal {
// 前序遍历：根 -> 左 -> 右
public void preorder(TreeNode root) {
if (root == null) return;
System.out.println(root.val); // 1. 访问根
preorder(root.left); // 2. 递归左
preorder(root.right); // 3. 递归右
}
}
李教授强调，不要死记硬背代码顺序，而是要想象成“剥洋葱”。每一层递归都在处理当前的节点，然后把剩下的子任务交给下一层。
1.2 力扣热题中的经典：二叉树的层序遍历
这道题（LeetCode 102）是面试必考题。它要求我们把树“按行”打印出来。这时候，递归就不太好使了，我们需要队列（Queue）。
这就像是在银行排队办业务，先来的人先处理。我们先把根节点放进队列，然后每次从队列头取一个节点，把它打印出来，再把它左右孩子放进队列尾巴。
import java.util.*;
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // 这一层有多少个节点
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(currentLevel);
}
return result;
}
注意那个for循环里的size变量。这是层序遍历的精髓：先固定这一层的数量，不要混入下一层的节点。李教授说，很多初学者在这里会犯错，导致层次混乱。
二、动态规划：从“笨办法”到“聪明办法”的进化
如果说二叉树考察的是你的空间想象力，那动态规划（Dynamic Programming, DP）考察的就是你的“备忘录”意识。
我刚开始学DP的时候，特别反感。我觉得：“这不就是递归加个缓存吗？有必要搞得那么玄乎？”直到我遇到了“爬楼梯”问题。
2.1 爬楼梯：DP的入门门票
题目很简单：你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶？
笨办法（暴力递归）：
爬到第n阶，要么是爬了1步（从n-1来），要么是爬了2步（从n-2来）。所以f(n) = f(n-1) + f(n-2)。
代码写出来很优雅，但运行起来巨慢，因为重复计算太多了。比如算f(5)要算f(4)，算f(4)又要算f(3)，这f(3)算了无数遍。
聪明办法（动态规划）： 既然重复计算很讨厌，那我就把算过的结果记在小本本上，下次再用到直接查。
public int climbStairs(int n) {
if (n <= 2) return n;
// dp[i] 表示爬到第i阶的方法数
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
}
return dp[n];
}
李教授在课上指着这个代码说：“看，这就是动态规划。它有两个核心：最优子结构（大问题拆成小问题）和重叠子问题（小问题会被重复计算）。我们用一个数组把小问题的答案存起来，这就叫‘记忆化’。”
2.2 背包问题：DP的“万恶之源”
如果你只学爬楼梯，面试肯定不够。力扣热题里最难啃的骨头，往往是“背包问题”。
这里我不得不提李教授的一个比喻，超级形象：背包问题就像是你去超市买东西，预算有限（背包容量），东西有价值（价值），你想知道怎么买能花最少的钱买到最多的价值，或者花有限的钱买最多的东西。
0-1背包问题（LeetCode 416 分割等和子集，虽然是变体，但核心一样）： 每个物品只能选一次。
状态定义：dp[i][j] 表示从前i个物品中选择，放入容量为j的背包，能获得的最大价值。
状态转移：
- 不选第i个物品：
dp[i][j] = dp[i-1][j] - 选第i个物品：
dp[i][j] = dp[i-1][j-weight[i]] + value[i] - 取两者最大值。
为了节省空间，我们通常会优化成一维数组：
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
int target = sum / 2;
// dp[j] 表示容量为j的背包能装下的最大和
int[] dp = new int[target + 1];
for (int num : nums) {
// 注意这里是倒序遍历！防止同一个物品被重复使用
for (int j = target; j >= num; j--) {
dp[j] = Math.max(dp[j], dp[j - num] + num);
}
}
return dp[target] == target;
}
关键点来了： 为什么是倒序遍历？李教授解释得非常透彻：“如果你正序遍历，当你计算dp[j]时，dp[j-num]可能已经在这轮循环中被更新过了，这意味着你把同一个物品放了两次。倒序遍历保证了我们用的是‘上一轮’的数据，也就是‘每个物品只能用一次’的约束。”
这句话，让我把0-1背包和完全背包（物品无限次使用）的区别彻底搞清楚了。
三、面试实战：当二叉树遇上动态规划
很多面试题会把这两个知识点结合起来。比如LeetCode 124题“二叉树中的最大路径和”。
这道题看起来是二叉树，但解法里藏着DP的思想。
题目： 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
思路： 对于每一个节点，我们要求以它为“转折点”的最大路径和。这个和由三部分组成：
- 节点本身的值。
- 左子树提供的最大贡献（如果是负数，就不取，相当于0）。
- 右子树提供的最大贡献（同理）。
我们用全局变量maxSum来记录遍历过程中出现的最大值。
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
// 返回以当前节点为起点，向下延伸的最大路径和
// 注意：只能选一边（左或右），因为路径不能分叉
private int dfs(TreeNode node) {
if (node == null) return 0;
// 如果子树贡献为负，就忽略它（取0）
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
// 当前节点作为“转折点”的路径和
int currentPathSum = node.val + left + right;
// 更新全局最大值
maxSum = Math.max(maxSum, currentPathSum);
// 返回给父节点的最大贡献（只能选一边）
return node.val + Math.max(left, right);
}
}
李教授说，这道题的难点在于区分“返回给父节点的值”和“当前节点能形成的最大路径”。返回给父节点的，只能是一条线（单分支）；而当前节点能形成的最大路径，可以是“V”字形（双分支）。这种“局部最优”与“全局最优”的分离，正是动态规划思想在树形结构上的体现。
四、给零基础同学的一点真心话
说实话，刚开始学这些的时候，我真的很焦虑。看着周围人刷完了多少题，自己连最简单的递归都写不顺。但李教授在第一课就说了：“算法不是智商测试，它是逻辑思维的训练。你不需要很聪明，你只需要很坚持。”
我的建议是：
- 不要追求速度，要追求理解。 一道题，花一个小时弄懂它的每一种情况，比机械地抄十道简单题有用得多。
- 画图！画图！画图！ 无论是二叉树的遍历，还是DP的状态转移，画出来之后，思路会清晰很多。我在笔记本上画过的图，大概能铺满半个书桌。
- 总结模板，但不要死记。 比如二叉树的中序遍历迭代写法，是一个经典模板；DP的背包问题，也有固定的状态转移思路。掌握模板可以帮你快速上手，但理解背后的原理才能帮你应对变体。
- 保持耐心，允许自己卡壳。 我卡壳的时候，会先去散步，或者洗个澡。很多时候，灵感是在你放松的时候突然冒出来的。
力扣热题100道，听起来很多，但其实真正核心的考点也就那么几十个。二叉树、动态规划、回溯、贪心，这四大天王，你吃透了，面试中的算法题基本就能应付自如了。
我记得有一次面试，面试官问了我一道动态规划题，是关于“打家劫舍”的变种。我下意识地在草稿纸上画出了状态转移的图，然后写出了那个dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])的公式。面试官点点头，说：“思路很清晰。”
那一刻，我突然想起李教授在课上的那句话：“当你把一道题看透，它就变成了一块砖，你可以用它在心里建起一座大厦。”
希望我的这些体会，能给你一点启发。算法这条路，走起来可能有点累，但沿途的风景，真的值得一看。加油！