검지offer의 면접문제 24: 두 갈래 나무와 어떤 값의 경로

제목:
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
예를 들어 다음 그림에서 두 갈래 트리와 정수 22를 입력하면 두 개의 경로가 인쇄됩니다. 첫 번째 경로는 결점 10, 12, 두 번째 경로는 결점 10, 5, 7을 포함합니다.
생각:
1. 뿌리 결점이 비어 있는지 판단
2. 단일 경로에vector path가 저장되어야 한다.
3. 여러 경로에vector>ret가 저장되고 되돌아와야 합니다.
4. 뿌리 결점에서 분석하면 매번 반복할 때마다 결점의 값을 먼저 방문해야 하기 때문에 앞의 순서를 반복한다.
5. 반복하는 동시에 방문한 결점의 값을 저장하고 expectNumber와 상쇄하여 나머지 expectNumber를 얻는다
6. 뿌리 결점만 마지막 값과 나머지 expectnumber를 판단하고 같지 않다.
7. 루트 결점이 같으면 귀속 종료 조건이다
코드:

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector > FindPath(TreeNode* root,int expectNumber) 
    {
		vector> ret;
        vector path;
        if(root==NULL)
        {
            return ret;
        }
        findLeaf(ret,path,root,expectNumber);
        return ret;
    }
    void findLeaf(vector> &ret,vector &path,TreeNode *node,int left)
    {
        path.push_back(node->val);
        // 
        if(left-node->val==0&&node->left==NULL&&node->right==NULL)
        {
            ret.push_back(path);
        }
        else
        {
            if(node->left)
            {
                int l=left-node->val;
                findLeaf(ret,path,node->left,l);
            }
            if(node->right)
            {
                int l=left-node->val;
                findLeaf(ret,path,node->right,l);
            }
        }
        // ，pop 
        path.pop_back();
    }
};

씬 버전 코드:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
    vector >allRes;
    vector tmp;
    void dfsFind(TreeNode * node , int left){
        tmp.push_back(node->val);
        if(left-node->val == 0 && !node->left && !node->right)
            allRes.push_back(tmp);
        else {
            if(node->left) dfsFind(node->left, left-node->val);
            if(node->right) dfsFind(node->right, left-node->val);
        }
        tmp.pop_back(); 
    }
public:
    vector > FindPath(TreeNode* root,int expectNumber) {
        if(root) dfsFind(root, expectNumber);
        return allRes;
    }
};