[leetcode]Path Sum--巧用遞歸

[leetcode]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減去當前節點的值，左子樹也進行同樣的處理。
代碼：

class Solution {
public:

    bool hasPathSum(TreeNode* root, int sum) {
        if(!root)
            return false;
        if(!root->left&&!root->right)
        {
            if(root->val==sum)
                return true;
            else
                return false;
        }
        return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
    }

};