LeetCode113. 경로 총 II

두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및sum = 22 ,

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

반환:

[
   [5,4,11,2],
   [5,8,4,5]
]

제목 분석: dfs를 사용하여 잎 노드까지 순서대로 훑어보십시오. 만약에sum가 저장된 경로가 있다면.본 문제의 관건은 언제 거슬러 올라가느냐에 있다. 하나는 잎 노드를 방문할 때 거슬러 올라가야 한다는 것이다.또 하나는 한 노드의 좌우 노드를 방문한 후에도 거슬러 올라가야 한다는 것이다.
코드 표시:

class Solution {
public:
    vector> pathSum(TreeNode* root, int sum) {
        vector> vec;
        vector temp;
        dfs(root,sum,temp,vec);
        return vec;
    }
    
    void dfs(TreeNode* root,int sum,vector& temp,vector>& vec){
        if(root==NULL)
            return;
        sum -= root->val;
        temp.push_back(root->val);
        if(root->left==NULL && root->right==NULL){
            if(sum == 0)
                vec.push_back(temp);
            temp.pop_back();
            return;
        }
        dfs(root->left,sum,temp,vec);
        dfs(root->right,sum,temp,vec);
        temp.pop_back();
    }
};