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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
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();
}
};