LetCode의 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 ,
두 갈래 나무의 제목은 귀환을 사용하는 것이 매우 간단합니다. 귀환식을 쓸 수만 있다면 ok입니다. 여기서 제가 사용하는 귀환식은 다음과 같습니다.
hasPathSum(root->left , sum-root->val)||hasPathSum(root->right,sum-root->val);
즉 왼쪽 트리나 오른쪽 트리가 조건에 부합되기만 하면true로 되돌아온다
여기에 곤란한 것이 하나 있다. 루트가null이라고 생각하기 시작했을 때sum는 0이었다. 정말이다...루트가 NULL인 줄도 모르고 false로 돌아갑니다...어이가 없어, 코드 두 줄이면 돼.하지만 이 코드는 전체 알고리즘의 정수이고,
두 줄 코드는 다음과 같습니다.
4

 bool hasPathSum(TreeNode *root, int sum) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        if(root==NULL) return (0==sum);
        else return hasPathSum(root->left , sum-root->val)||hasPathSum(root->right,sum-root->val);    
    }

학습 슬래그는 바로 학습 슬래그이다. 이렇게 하지 못하게 하려면 각각 판단해야 한다. 특히 귀환을 이용할 때 귀환 상황을 자세히 고려해야 한다. 나는 네 가지로 나뉜다.
1 좌우가 비어 있지 않습니다. 좌우 서브트리의 bool 값의 합계를 되돌려줍니다.
2 모두 비어 있습니다. 이 노드를 판단하는val과sum의 동일한 판단을 되돌려줍니다
3 왼쪽이 비어 있지 않으면 왼쪽 트리의 bool 값을 되돌려줍니다
4 오른쪽이 비어 있지 않으면 오른쪽 트리의 bool 값을 되돌려줍니다
여기서 주의해야 할 것은 이곳의 값은 노드 수가 아니라 각 노드의val의 값의 합이기 때문에 줄일 때 주의해야 한다
코드는 다음과 같습니다. 60ms

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        //if(root==NULL) return (0==sum);
        //else return hasPathSum(root->left , sum-1)||hasPathSum(root->right,sum-1);
        if(root==NULL) return false;
        
        if(root->left != NULL && root->right != NULL){
            // ， 。。。 1， root->val
            return hasPathSum(root->left , sum-root->val)||hasPathSum(root->right,sum-root->val);
        }
        else if(root->left == NULL && root->right == NULL ){
             // ， root->val   sum 
            return (root->val==sum);
        }
        else if(root->left != NULL){
            // ， root->left   sum 
            return hasPathSum(root->left,sum-root->val) ;
        }
        else {
            // ， root->right   sum 
            return hasPathSum(root->right,sum-root->val) ;
        }
        
    }

};