112. 路径总和

使用递归来解题，如上图中寻找22，即相当于在5的左右子树上寻找是否存在和为17的路径，递归寻找，在4的左右子树中寻找是否存在路径和为13

对于上面的代码需要注意的是递归的终止条件
在root的左子树中寻找5-5=0的结果，并且此时左子树为null,所以返回true
但是不符合题意，这里寻找的是从根到叶子的路径 此时5到左子树null并不是到叶子节点

递归终止条件不应该是node==null，而应该判断此时root是否为一个叶子节点，
即其左右子树都为空

code

 public boolean hasPathSum(TreeNode root, int sum) {
         //如果为空节点 直接返回false
        if(root==null)
            return false;
        //递归的终止条件 判断叶子节点的值是否等于此时的sum
        if(root.left == null && root.right == null)
            return sum == root.val;
        //在左子树中寻找是否存在和为sum-root.val的路径
        if(hasPathSum(root.left, sum-root.val))
            return true;
        //在右子树中寻找是否存在和为sum-root.val的路径
        if(hasPathSum(root.right, sum-root.val))
            return true;
        //都没有找到 则返回false
        return false;
    }