二叉树 DFS：递归框架与路径问题

二叉树递归的万能框架

所有二叉树 DFS 问题都可以套这两个框架：

框架一：回溯（先序遍历位置做决策）

void dfs(TreeNode node, /* 路径信息 */ ...) {
    if (node == null) return;
    // 做选择（进入节点）
    dfs(node.left, ...);
    dfs(node.right, ...);
    // 撤销选择（离开节点）
}

框架二：分解（后序遍历位置汇总结果）

int solve(TreeNode node) {
    if (node == null) return 0;        // base case
    int left = solve(node.left);       // 左子树返回值
    int right = solve(node.right);     // 右子树返回值
    return /* 利用 left, right 计算 node 的答案 */;
}

路径类问题

路径总和（LeetCode 112）

判断是否存在根到叶子的路径，使其路径和为 target：

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

路径总和 II（LeetCode 113）

回溯框架收集所有满足条件的路径：

List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), res);
    return res;
}

void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
    if (node == null) return;
    path.add(node.val);                             // 做选择
    remain -= node.val;
    if (node.left == null && node.right == null && remain == 0) {
        res.add(new ArrayList<>(path));             // 记录答案
    }
    dfs(node.left, remain, path, res);
    dfs(node.right, remain, path, res);
    path.remove(path.size() - 1);                   // 撤销选择（回溯）
}

二叉树中的最大路径和（LeetCode 124）

路径可以不经过根节点，从树中任意节点到任意节点。 关键：每个节点「贡献」给父节点的只能是单边（左或右），但自身记录的答案可以穿过两边。

int maxSum = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}

int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, dfs(node.left));    // 负贡献直接舍弃
    int right = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, left + right + node.val);  // 穿过本节点的最大路径
    return Math.max(left, right) + node.val;             // 向父节点只能选一侧
}

树形结构属性

平衡二叉树（LeetCode 110）

后序遍历，子树先算高度再判断：

boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

int height(TreeNode node) {
    if (node == null) return 0;
    int lh = height(node.left);
    int rh = height(node.right);
    if (lh == -1 || rh == -1) return -1;          // 子树已失衡
    if (Math.abs(lh - rh) > 1) return -1;         // 当前节点失衡
    return Math.max(lh, rh) + 1;
}

二叉树的直径（LeetCode 543）

直径 = 左子树最深 + 右子树最深，遍历每个节点取最大：

int diameter = 0;

int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return diameter;
}

int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left);
    int right = depth(node.right);
    diameter = Math.max(diameter, left + right);   // 经过本节点的直径
    return Math.max(left, right) + 1;
}

最近公共祖先（LeetCode 236）

后序遍历，从下往上汇报：

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;              // 都在同侧（或只有一个）
}

路径 vs 属性 对比