CodingInterview-二叉树中和为某一值的路径

这道题主要使用基于 DFS 的回溯算法，首先对树进行遍历，在遍历的过程中遇到符合条件的树就将其路径加入返回的 vector 中，并将一些不符合情况的条件进行剪枝。

最后，由于要求按路径从长到短排序，所以还需要使用自定义的排序函数进行排序。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
private:
    vector<int> path;
    int sum;
    vector<vector<int>> result;
    int expectNumber;
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        this->expectNumber=expectNumber;
        FindPath(root);
        sort(result.begin(),result.end(),vectorSort);
        return result;
    }
    void FindPath(TreeNode* p){
        if(p==NULL) return;
        if(sum>expectNumber) return;
        sum+=p->val;
        path.push_back(p->val);
        if(sum==expectNumber){
             if(p->left==NULL && p->right==NULL){
                 vector<int>* newPath=new vector<int>(path);
                 result.push_back(*newPath);
             }
        }else{
            FindPath(p->left);
            FindPath(p->right);
        }
        sum-=p->val;
        path.pop_back();
    }
    bool static vectorSort(vector<int> a,vector<int> b){
        return a.size()>b.size();
    }
};