검 지 Offer - (24) 이 진 트 리 와 특정한 값 의 경로

제목 설명:
이 진 트 리 와 정 수 를 입력 하고 이 진 트 리 의 노드 값 과 정 수 를 입력 하기 위 한 모든 경 로 를 출력 합 니 다.경 로 는 나무의 뿌리 결점 에서 부터 잎 결점 이 지나 가 는 결점 까지 하나의 경 로 를 형성 하 는 것 으로 정의 된다.
다음 과 같이 구현:

//                                 
//     root      
//     ，           vector     ，      vetor push_back pop  
//  ：
//1.                   ，             。        pop
//2.         pop
class Solution
{
public:
    vector<int> valueVec;//          
    vector<vector<int> > allPathVec;//         
    int currentNumber = 0;//     
    void Path(TreeNode *root, int expectNumber, int &currentNumber)
    {
        if (root == NULL) return;//     
        valueVec.push_back(root->val);//          
        currentNumber += root->val;//     

        if (currentNumber == expectNumber && root->left == NULL && root->right == NULL)//                      
        {
            allPathVec.push_back(valueVec);//     
            return;//      
        }
        else//        left right
        {
            Path(root->left, expectNumber, currentNumber);
            Path(root->right, expectNumber, currentNumber);
            currentNumber -= valueVec.back();//      pop
            valueVec.pop_back();//       
        }
        if (root->left != NULL || root->right != NULL)//         
        {
            //     ，                   
            currentNumber -= valueVec.back();
            valueVec.pop_back();
        }
    }
    vector<vector<int> > FindPath(TreeNode* root, int expectNumber) 
    {
        if (root == NULL) return allPathVec;//     
        Path(root, expectNumber, currentNumber);//    
        return allPathVec;
    }
};