题解 | #二叉树中和为某一值的路径(一)#

二叉树中和为某一值的路径(一)

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return bool布尔型
 */
function hasPathSum(root, sum) {
    // write code here
    if (!root) return false;

    return find(root, sum - root.val);
}

function find(node, count) {
    // 终止条件
    if (!node.left && !node.right) {
        return count === 0;
    }
    // 还没到叶子节点,存在左子节点,就去递归看左边的路径情况
    if (node.left) {
        if(find(node.left, count - node.left.val)) return true;
    }
    // 还没到叶子节点,存在右子节点,就去递归看右边的路径情况
    if(node.right) {
        if(find(node.right, count - node.right.val)) return true;
    }
    // 上述情况都没有的情况下就返回false
    return false;
}

module.exports = {
    hasPathSum: hasPathSum,
};

求从根节点到叶子节点是否存在一条路径使得路径和等于给定的sum。

深度搜索递归回溯,每次往下走一个节点,count -= node.val,终止的条件就是判断是否走到了叶子节点(!node.left && !node.right),走到了叶子节点之后有两种情况,此时count 等不等于0,等于0说明这条路径可行,否则不行。

下面两个递归,一个节点可行可不行,就是判断它的左右两个节点是否有返回true的,如果左子树边路径返回了true,那就说明左边路径可行,右子树同理。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 13:15
点赞 评论 收藏
分享
北漂的牛马人:211佬,包进的,可能是系统问题
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务