|
一、问题描述
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
样例
给定一个二叉树，和 目标值 = 5:
1
/ \
2 4
/ \
2 3
返回：
[
[1, 2, 2],
[1, 4]
]
二、解题思路
设置vector向量存储当前的路径v，若当前路径和等于目标值，则存储进去，所以我们要定义一个find函数，当路径和等于目标值且左右子树都为空时，把当前的v存储进去，当左子树或右子树不为空时，继续查找，直到路径和等于目标值，此外还要注意查找完一条路径，v要清空，路径和s也随着路径的变化而变化。
三、我的代码
class Solution {
public:
/**
* @param root the root of binary tree
* @param target an integer
* @return all valid paths
*/
vector<vector<int>>P;
vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
vector<int>v;
int s=0;
find(root,target,v,s);
return P;
}
void find(TreeNode *root,int target,vector<int>v,int s)
{
if(root!=NULL)
{
v.push_back(root->val);
s=s+root->val;
if(s==target&&root->left==NULL&&root->right==NULL)
{
P.push_back(v);
}
if(root->left!=NULL)
{
find(root->left,target,v,s);
}
if(root->right!=NULL)
{
find(root->right,target,v,s);
}
s=s-root->val;
v.pop_back();
}
}
};
四、我的感想
继上次课之后，老师讲过求所有路径，大概对怎么样求路径有一个了解，求二叉树的路径和也与其类似，只要找到路径和与目标值相等的路径即可，在这过程中也遇到了很多困难，因一些错误老是出现run time error，还是因为自己不够熟练，知识掌握太少，以后要更加努力了。 | 
转播
