描述
来源：牛客-名企高频面试题高频TOP200
输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
数据范围:
树中节点总数在范围 [0, 5000] 内
-1000 <= 节点值 <= 1000
-1000 <= expectNumber <= 1000
答案及解析
DFS, 解决方式就是从根节点往下走的时候，将每个路径存入数组，然后遍历路径的和，找出匹配的路径。
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
| vector<vector<int>> vVec;
vector<int> vec;
int GetSum(vector<int> v)
{
int sum = 0;
for(auto i : v)
sum += i;
return sum;
}
void GetEqual(TreeNode* root)
{
if(!root)
return;
vec.push_back(root->val);
if(!root->left && !root->right)
vVec.push_back(vec);
GetEqual(root->left);
GetEqual(root->right);
vec.pop_back();
}
vector<vector<int>> FindPath(TreeNode* root,int expectNumber)
{
GetEqual(root);
vector<vector<int>> res;
for(auto i : vVec)
{
if(GetSum(i) == expectNumber)
res.push_back(i);
}
return res;
}
|
时间复杂度：O(N), 为二叉树节点数
空间复杂度：O(N^2), 使用二维数组
