[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);
    }

};