题解 | #JZ34 二叉树中和为某一值的路径#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<vector<int> > paths;
    
    void trace(TreeNode *root, vector<int> &path, int remain) {
        if (root->left == nullptr && root->right == nullptr) {
            if (remain == root->val) {    //等于期望值加入路径
                path.push_back(root->val);
                paths.push_back(path);
                path.pop_back();    //回退
            }
            return;
        }
        
        int val = root->val;

        remain -= val;
        path.push_back(val);

        if (root->left) trace(root->left, path, remain);    //遍历左子树
        if (root->right) trace(root->right, path, remain);    //遍历右子树

        remain += val;    //剩余值和路径均回退
        path.pop_back();
    }
    
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<int> path;
        
        paths.clear();
        
        if (root) trace(root, path, expectNumber);
        
        return paths;
    }
};