代码随想录算法训练营第15天｜二叉树Part03

记录题目：

• 路径总和
• 路径总和 II
• 二叉树的最近公共祖先

如何判断递归函数是否需要返回值？

• 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值， 因为遇到符合条件的路径了就要及时返回，通常可以用布尔类型表示。

• 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。

• 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。

• 路径总和

• 路径总和 II

• 二叉树的最近公共祖先

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

LeetCode112. 路径总和

返回值为布尔类型：

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
let hasPathSum = function (root, targetSum) {
  if (!root) return false;
  // 当前节点是叶子节点，检查路径和是否正好为 targetSum
  if (!root.left && !root.right && root.val === targetSum) return true;
  // 向左右子树递归查找
  return hasPathSum(root.left, targetSum - root.val) ||
         hasPathSum(root.right, targetSum - root.val);
};

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

LeetCode113. 路径总和 II

无返回值：

var pathsum = function(root, targetsum) {
    let respath = [], curpath = [];
    const traveltree = function(node, count) {
        curpath.push(node.val);
        count -= node.val;
        if(node.left === null && node.right === null && count === 0) {
            respath.push([...curpath]);
        }
        node.left && traveltree(node.left, count);
        node.right && traveltree(node.right, count);
        let cur = curpath.pop();
        count -= cur;
    }
    if(root === null) {
        return respath;
    }
    travelTree(root, targetSum);
    return resPath;
};

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

LeetCode236. 二叉树的最近公共祖先

返回值为目标节点：

var lowestCommonAncestor = function(root, p, q) {
    const dfs = function(node) {
        if (node === null || node === p || node === q) return node;
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left && right) return node;
        return left || right;
    };
    return dfs(root);
};

太好了，你已经更新了代码部分，下面我将按照我上面建议的风格继续修改你的文档内容，保持统一、专业、清晰，并删除冗余，精炼结构。

---

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

根据百度百科的定义： “对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（即离两者最近）。”

LeetCode [https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/) 236. 二叉树的最近公共祖先

解法：递归 + 后序遍历

var lowestCommonAncestor = function(root, p, q) {
    const dfs = function(node) {
        if (node === null || node === p || node === q) return node;
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left && right) return node;
        return left || right;
    };
    return dfs(root);
};

思路分析

该算法使用了后序遍历（即“左右中”的遍历顺序），核心思想是：

从底向上回溯，判断当前节点是否为 p 和 q 的最近公共祖先。

为什么可以不显式遍历两个节点？

如果 p 是 q 的祖先，递归在访问到 p 时就会返回 p，而不会继续显式地遍历 q。

但这并不会影响正确性。因为：

• 我们关心的是：当前节点的左子树是否包含一个目标节点，右子树是否包含另一个；
• 如果只在一个子树中找到了一个非空结果，就继续返回那个节点；
• 如果两边都找到了非空结果，说明当前节点正好是两者交汇点，即最近公共祖先。

换句话说，返回值的传递就是信息的传播路径，而不是访问状态的标记。

为什么用后序遍历？

这个问题的本质是从子树结果中“归纳”出当前节点是否满足祖先条件，这是后序遍历的典型应用场景。

后序遍历的结构：先处理左子树 → 再处理右子树 → 再处理当前节点

这样的遍历方式可以确保：

• 当前节点能拿到左右子树的返回信息；
• 决策当前节点是否是“最近公共祖先”时，信息已就绪；
• 实现“从叶子节点向根汇总”的逻辑判断。

总结：后序遍历适用场景

后序遍历适合处理以下类型问题：

问题类型	是否适用	理由
当前节点决策依赖子树结果	✔	需要知道左右子树是否含有目标节点后，才能判断当前是否是祖先
子树结果需要合并	✔	如计算树高、路径和等，左右结果参与当前计算
只需遍历所有节点	✘	如遍历打印、序列化等，前序/中序遍历更直接简洁