Path Sum,Path Sum II,Path Sum III总结
程序员文章站
2022-05-19 10:45:47
...
【Path Sum I】
「运行结果」
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL)
return false;
else if (root->left == NULL && root->right == NULL && root->val == sum)
return true;
else {
return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum - root->val);
}
}
};
【Path Sum II】
「思路」深度优先遍历,用sum-root->val(每个节点的值)将每次sum减完的结果分为:
有后续,超过结果 1 sum<0
不够 2
无后续,超过结果 1 sum<0
刚刚好 3
不够 1 root == NULL
并将其归类为1 2 3三种。
「出现过的错误」
1.将无后续 不够 的条件写成 root == NULL | sum<0,没有考虑到目标数为负数。
2.将无后续 不够 的条件写成 (root == NULL&&sum!=0) | sum<0
导致member access within null pointer of type 报错,错误在于当root=null且sum=0时,第一个不会return,所以会进去第二个判断,null是没有left right的,就会出现空指针的问题。
「运行结果」
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum)
{
//vector<vector<int>> ret;
vector<vector<int>>* ret = new vector<vector<int>>();
if(root == NULL)
{
return *ret;
}
vector<int> ans;
pathsum(ret,ans,root, sum);
return *ret;
}
/*
有后续,超过结果 1 sum<0
不够 2
无后续,超过结果 1 sum<0
刚刚好 3
不够 1 root == NULL
*/
private:
void pathsum( vector<vector<int>>* ret,vector<int>ans,TreeNode* root,int sum)
{
if (root == NULL) //1
{
return;
}
else if (root->left == NULL && root->right == NULL && root->val == sum) //3
{
ans.push_back(root->val);
ret->push_back(ans);
}
else //2
{
ans.push_back(root->val);
pathsum(ret,ans,root->left, sum - root->val);
pathsum(ret,ans,root->right, sum - root->val);
}
}
};
【Path Sum III】
「思路」
利用了前序遍历,对于每个遍历到的节点进行处理,维护一个变量ans来记录之前路径之和,然后cur为ans加上当前节点值,如果cur等于sum,那么返回结果时要加1,然后对当前节点的左右子节点调用递归函数求解。pathSum相当于对数广度的遍历,path相当于深度搜索相加。
「运行结果」
class Solution {
public:
int pathSum(TreeNode* root, int sum) {//广度
if(!root)
{
return 0;
}
return path(root,sum,0)+pathSum(root->left,sum)+pathSum(root->right,sum);
}
int path(TreeNode* root,int sum,int ans)//深度
{
if(!root)
{
return 0;
}
int cur=ans+root->val;
if(cur==sum)
return 1+path(root->left,sum,cur)+path(root->right,sum,cur);
else return path(root->left,sum,cur)+path(root->right,sum,cur);
}
};
「后记」
做这个题的时候我一开想的用动态规划做,但是苦于找不到边界条件和合适的增量,求助于一位学长。虽然他的方法也不是动态规划,但是近似,都是通过记录,然后最后遍历。虽然效率不高,但是值得借鉴,代码和结果如下:
ps.如果你知道用动态规划的方法写这个程序请留言,谢谢!