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

/*
 * 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，那就说明左边路径可行，右子树同理。