题目链接：Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and sum = 22,

              5 
             / \ 
            4   8 
           /   / \ 
          11  13  4 
         /  \      \ 
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

这道题的要求是判断二叉树中是否存在根节点到叶子节点的路径之和等于给定的sum。

递归思路，如果当前节点为NULL，返回0；如果当前节点的左右子树均为NULL，则直接判断val是否等于sum；剩下情况，用sum减去val，然后递归处理左右子树。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution
{
public:
    bool hasPathSum(TreeNode *root, int sum)
    {
        if(root == NULL)
            return false;
        
        if(root -> left == NULL && root -> right == NULL)
            return root -> val == sum;
        
        return hasPathSum(root -> left, sum - root -> val)
            || hasPathSum(root -> right, sum - root -> val);
    }
};