本文为剑指 offer 系列第二十六篇。
主要知识点为二叉树，在二叉树的遍历的基础上去判断是否有存在路径之和等于定值。
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
解题思路
- 从最简单的情况开始考虑，如果树只有一个根结点，那么我们只要判断这个节点的值是不是只要等于目标值target即可。
- 再复杂一点，如果有三个节点，根节点和左右子节点。那么我们我们在其实就相当于在子节点中判断值是不是等于目标值减去根节点的值即可。其实等价于简化到了第一种情况——单个节点。
- 如果层数继续加深，最后的判断其实还是等价于在最后一层判断节点的值是否等于目标值减去整个路径上所有的节点的值。
- 思想类似于前序遍历，只是本来的打印变成了节点条件的判断放到了最后的叶子结点一层，然后每一层向下一层遍历的时候需要更改期待值。
既然是前序遍历就可以用递归和非递归两种方式来解决这个问题。
解题代码
代码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
| /*
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) {
if(root==NULL)
return res;
temp.push_back(root->val);
if((expectNumber-root->val)==0 && root->left==NULL && root->right==NULL)
{
res.push_back(temp);
}
FindPath(root->left,expectNumber-root->val);
FindPath(root->right,expectNumber-root->val);
if(tmp.size()!=0){
temp.pop_back();
}
return res;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
代码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
| /*
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) {
if(!root) return res;
vector<int> temp;
helper(root,expectNumber,temp);
return res;
}
void helper(TreeNode* root,int expectNumber,vector<int> temp){
if(!root || expectNumber < 0) 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);
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！