Problem: 112. 路径总和

作者:江月迟迟

发表于:2024-12-10

字数统计:327 字

预计阅读2分钟

[TOC]

思路

一般递归的写法是第一个版本，这里我在化简的时候不小心错误处理，判false的情况其实有两种，第一种是node.child === null， 第二种是node.child不是路径，所以在return (left || right) ? true : node.left === null && node.right === null && carry + node.val === targetSum 的语句中，需要将第二种情况摘出来判断。

Code

var hasPathSum = function(root, targetSum) {
    return dfsSum(root, 0, targetSum);
};

var dfsSum = function(node, carry, targetSum) {
    // 节点为空时返回false
    if (node === null) {
        return false;
    }

    // 到达叶子节点时，检查路径和是否等于目标和
    if (node.left === null && node.right === null) {
        return node.val + carry === targetSum;
    }

    // 递归遍历左右子树，并更新路径和
    const left = dfsSum(node.left, carry + node.val, targetSum);
    const right = dfsSum(node.right, carry + node.val, targetSum);

    // 如果左右子树中有一条路径满足条件，则返回true
    return left || right;
};


var dfsSum = function(node, carry, targetSum) {
    // node判空
    if (node === null) {
        return false
    }
    // 往下递推
    const left = dfsSum(node.left, carry + node.val, targetSum)
    const right = dfsSum(node.right, carry + node.val, targetSum)
    return (left || right) ? true : node.left === null && node.right === null && carry + node.val === targetSum
}