本文为剑指 offer 系列第二十六篇。
主要知识点为二叉树，在遍历的基础上判断是否存在路径之和等于定值。
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
解题思路
- 从最简单的情况开始考虑，如果树只有一个根结点，那么只要判断这个节点的值是否等于目标值target即可。
- 再复杂一点，如果有根节点和左右两个叶子节点，那么在叶子节点处判断的目标值就变成了target减去根节点的值。
- 如果层数继续加深，也可以每向下一层就减去当前节点的值，直到叶子节点，再判断它是否等于剩余的目标值。节点可能为负数，所以剩余目标值小于0时也要继续遍历。
- 遍历时保存当前路径，满足条件就加入结果，最后把较长的路径排在前面。
这个过程和前序遍历类似，可以用递归来实现。下面给出两种保存路径的写法：一种共用temp并在返回时回退，另一种把temp作为参数传递。
解题代码
代码1:用成员变量temp保存路径
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
| /*
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>> res;
vector<int> temp;
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
res.clear();
temp.clear();
helper(root,expectNumber);
stable_sort(res.begin(),res.end(),[](const vector<int>& a,const vector<int>& b){
return a.size() > b.size();
});
return res;
}
void helper(TreeNode* root,long long expectNumber){
if(root==NULL) return;
temp.push_back(root->val);
if(expectNumber == root->val && root->left==NULL && root->right==NULL){
res.push_back(temp);
}
helper(root->left,expectNumber-root->val);
helper(root->right,expectNumber-root->val);
temp.pop_back();
}
};
|
设n为节点数、h为树高、p为结果路径数、L为所有结果路径的总长度。时间复杂度为O(n+L+p*log(p+1))，空间复杂度为O(h+L)，包含保存结果和按长度排序的开销。
代码2:通过参数传递路径
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
| /*
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>> res;
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
res.clear();
if(!root) return res;
vector<int> temp;
helper(root,expectNumber,temp);
stable_sort(res.begin(),res.end(),[](const vector<int>& a,const vector<int>& b){
return a.size() > b.size();
});
return res;
}
void helper(TreeNode* root,long long expectNumber,vector<int> temp){
if(!root) return ;
temp.push_back(root->val);
if(root->val == expectNumber && root->left == NULL && root->right == NULL){
res.push_back(temp);
}
if(root->left) helper(root->left,expectNumber-root->val,temp);
if(root->right) helper(root->right,expectNumber-root->val,temp);
}
};
|
沿用上面的n、h、p、L记号。这里每次按值复制temp，时间复杂度上界为O(nh+L+plog(p+1))，空间复杂度为O(h^2+L)。链状树会同时保存长度逐层增加的路径副本。
以上，本题结束！