树算法：从遍历到最近公共祖先

重新整理“树算法：从遍历到最近公共祖先”时，我先翻了自己以前的错误记录，其中最典型的一条就是：树题里我经常能写出遍历，却不知道信息应该从父节点往下传，还是从子树往上汇总。沿着这个问题再看原理和代码，比直接背结论清楚得多。

树算法连接了数据结构和算法两部分。前面学树结构时，我们关注节点如何组织；到了算法篇，我们更关注如何遍历、统计、寻找路径和合并子树状态。

树的问题通常有一个特点：父子关系天然递归，所以很多树算法都可以从“当前节点要向上返回什么”来思考。

树算法路线

图：树算法从遍历开始，逐步进入路径和子树状态

常见树算法：

前序、中序、后序遍历。
层序遍历。
求深度、高度、节点数。
路径和、直径。
二叉搜索树查询和范围遍历。
最近公共祖先 LCA。
树形动态规划。

三种 DFS 遍历

void preorder(TreeNode root) {
    if (root == null) return;
    visit(root);
    preorder(root.left);
    preorder(root.right);
}

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    visit(root);
    inorder(root.right);
}

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    visit(root);
}

前序适合自顶向下传状态；后序适合先拿到子树结果，再计算当前节点；中序在 BST 中可以得到有序序列。

层序遍历

层序遍历使用队列：

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            level.add(cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        ans.add(level);
    }
    return ans;
}

层序适合按层输出、最短层数、宽度统计。

树的高度和直径

求高度：

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

树的直径是任意两点之间最长路径。每个节点都可能作为最高拐点：

int ans = 0;

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

这是典型后序：先知道左右子树深度，再更新当前答案。

最近公共祖先 LCA

普通二叉树 LCA：

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;
}

如果左右子树分别找到目标，当前节点就是最近公共祖先；否则答案在找到目标的一侧。

BST 的 LCA 可以利用有序性：

TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
    return null;
}

树形 DP

树形 DP 的核心是：每个节点从子节点拿状态，再计算自己的状态。

比如打家劫舍 III，每个节点有两个状态：

偷当前节点。
不偷当前节点。

int[] dfs(TreeNode root) {
    if (root == null) return new int[]{0, 0};
    int[] left = dfs(root.left);
    int[] right = dfs(root.right);
    int rob = root.val + left[1] + right[1];
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{rob, notRob};
}

树形 DP 的关键是返回值设计。如果当前节点需要的信息没有从子树返回，后面就会很别扭。

常见错误

混淆深度和高度。
后序问题写成前序，导致拿不到子树结果。
层序遍历没有按层记录 size。
LCA 没考虑节点不存在的情况。
BST 题没有利用有序性。
递归深度过大导致栈溢出。

工程场景

组织架构、菜单、目录树。
评论楼中楼。
权限继承。
文件系统扫描。
AST 抽象语法树分析。
前端路由树。

树结构工程中经常要处理软删除、排序、懒加载和权限过滤。算法题里的树是干净的，业务里的树往往会有残缺节点和循环脏数据，所以服务端要做防御。

面试题

前序、中序、后序分别适合什么问题？
为什么树的直径适合后序遍历？
普通二叉树 LCA 和 BST LCA 有什么区别？
树形 DP 的状态应该怎么设计？
递归处理业务树时如何防止脏数据导致死循环？

小结

树算法的核心是递归状态。想清楚当前节点要做什么、从子树拿什么、向父节点返回什么，就能解决大部分树题。前序偏传递状态，后序偏汇总状态，层序偏按层扩散。