解题思路

• 临界条件：叶子节点（左右子树为空）
• 满足条件：路径之和为sum

解题步骤

• 左右子树同时递归查找，找到一个满足条件，即为找到，故左右子树的递归查找用“或”连接
• 递归查找时，抛去根节点的值，左右子树继续向下查找
• 当叶子节点且节点值等于sum找到

注意

• 临界条件
• 注意审题，二叉树中的值可以为负值，故sum可以为 0或者负值

/*
 * 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;
    // 定义递归函数
    function findSum(proot,sum){
        // 特殊情况，空树
        if(!proot)
            return false;
        // 叶子节点，且节点值符合要求，找到了！！！
        if(!proot.left && !proot.right && proot.val==sum)
            return true;
        // 没找到，继续向下递归查找，左子树或右子树找到一条便返回true
        return findSum(proot.left,sum-proot.val)||findSum(proot.right,sum-proot.val);
    }
    // 调用递归函数
    return findSum(root,sum);
}
module.exports = {
    hasPathSum : hasPathSum
};