이 진 트 리 옮 겨 다 니 기: 이 진 트 리 의 모든 노드 를 합 치 는 두 가지 방법 (2)

방법 1, 이 진 트 리 의 높이 를 구 하 는 것 과 유사 하 며, 반환 값 이 있 습 니 다.
함수 에서 재 귀적 호출 을 보고 되 돌아 오 는 상황 을 볼 때 보통 아래 에서 위로 이해 하고 정리 하 는 것 이 좋 습 니 다.아래 의 두 문장 처럼 마지막 에 모두 귀속 에서 효과 가 생 겼 다.

 lsum=Sum(T->left);
 rsum=Sum(T->right);

int Sum(TreeNode* T){
        if(T==NULL)return 0;
        int sum=0;
        int lsum,rsum;
        lsum=Sum(T->left);
        rsum=Sum(T->right);
        sum=T->val+lsum+rsum;
        return sum;
    }

방법 2. 외부 변 수 를 이용 하여 옮 겨 다 닐 때마다 방문 하여 외부 변 수 를 수정 합 니 다.
함수 호출 에서 되 돌아 오지 않 았 습 니 다. 위 에서 아래로 이해 할 수 있 습 니 다. 물론 아래 에서 위로 이해 할 수도 있 습 니 다. 이것 은 트 리 의 이동 과 유사 합 니 다.

int Sum(TreeNode* T,int& sum){
        if(T==NULL)return 0;
        sum+=T->val;
        Sum(T->left,sum);
        Sum(T->right,sum);
    }

전형 적 인 예제 leetcode 437

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(root==NULL)return 0;
        int count=0;
        helper(root,sum,count);
        int lres,rres;
        lres=pathSum(root->left,sum);
        rres=pathSum(root->right,sum);
        return count+lres+rres;
    }
    void helper(TreeNode* T,int sum,int& count){
        if(T==NULL)return;
        int res=sum-T->val;
        if(res==0)count++;
        helper(T->left,res,count);
        helper(T->right,res,count);
    }
    
};