总和系列总结 leetcode"/>
Path Sum路径总和系列总结 leetcode
Path Sum
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5/ \4 8/ / \11 13 4/ \ \7 2 1
返回 true
, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2
。
bool hasPathSumCore(TreeNode* root,int &sum_cur, int sum,bool& flag) {if (flag) {return true;}if (!root) {return false;}if (root && !root->left && !root->right && (sum_cur + root->val) == sum) {return true;}sum_cur += root->val;bool left = hasPathSumCore(root->left, sum_cur, sum,flag);if (!left) {sum_cur = sum_cur - (root->left ? root->left->val : 0);}bool right = hasPathSumCore(root->right, sum_cur, sum,flag); if (!right) {sum_cur = sum_cur - (root->right ? root->right->val : 0);}flag = left || right;return flag;}bool hasPathSum(TreeNode* root, int sum) {if (!root) {return false;}int sum_cur = 0;bool flag = false;return hasPathSumCore(root, sum_cur, sum,flag);}
Path Sum II
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5/ \4 8/ / \11 13 4/ \ / \7 2 5 1
返回:
[[5,4,11,2],[5,8,4,5] ]
思路:
和第一题类似,只是需要把找到的节点记录下来且是满足条件的所有节点,所以需要一个变量tmp来添加每一次访问到的从根节点到当前节点的路径,如果路径对应权值相加是答案且当前节点是叶节点,则把当前tmp添加到res中。这里写递推公式的注意下:
tmp.push_back(root->val);
在调用子节点递归函数之后要记得把tmp的值pop出来,因为就算把函数hasPathSumCore的tmp设置成引用,tmp返回父节点时也会修改成子节点修改后的样子,所以对于tmp需要在调用子节点后pop一下:
tmp.pop_back();
而相反的,记录当前累加和的sum_cur,如果函数hasPathSumCore声明的sum_cur是int &引用,那么sum_cur在调用完子节点后也是需要减去的,但是如果声明是int,那就不需要减去,如下图:
情况一:函数签名(sum_cur为引用):
hasPathSumCore(TreeNode* root, int &sum_cur, int sum, vector<vector<int>> &res, vector<int>&tmp)
那么函数调用为:
tmp.push_back(root->val);sum_cur += root->val;hasPathSumCore(root->left, sum_cur, sum, res, tmp); hasPathSumCore(root->right, sum_cur, sum, res, tmp);if (!root->left && !root->right && sum_cur == sum) {res.push_back(tmp);}tmp.pop_back();sum_cur-= root->val;
情况二:函数签名(sum_cur是普通类型):
hasPathSumCore(TreeNode* root, int sum_cur, int sum, vector<vector<int>> &res, vector<int>&tmp)
那么函数调用为:
tmp.push_back(root->val);sum_cur += root->val;hasPathSumCore(root->left, sum_cur, sum, res, tmp); hasPathSumCore(root->right, sum_cur, sum, res, tmp);if (!root->left && !root->right && sum_cur == sum) {res.push_back(tmp);}tmp.pop_back();
这些细节希望大家注意,对于递归调用如果少了
细节的考虑或者
边界条件判断,则往往容易在调用中层层出错,最后返回莫名其妙的结果。
Path Sum III
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 810/ \5 -3/ \ \3 2 11/ \ \ 3 -2 1返回 3。和等于 8 的路径有:1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
思路:
方法一:这道题开始怎么写都没想出来,各种报错,主要是这次条件不是从根节点到叶节点,条件放宽了,所以对于如下的树结构:
10/ \5 -3/ \ \3 2 11/ \ \ 7 -2 1
我们用前序遍历访问时,第一次根->叶的访问节点为序列A:10->5->3->7,对于这个序列中我们任意连续子序列的组合都可能等于8(sum),所以我们还是用类似“动态规划”的思想,来思考访问到当前节点和前一个节点时对结果有什么影响,有什么递推关系?当访问到3时,序列B为10->5->3,那么加上节点7后,和为8的情况只有10~7四个节点和,依次减去10,5,3后是否和为sum,所以访问到当前节点我们都会和依次减掉根节点开始的节点。代码如下:
void pathSumCore(TreeNode* root, int sum, int curSum, int &res, vector<TreeNode*> &vec) {if (!root) {return;}curSum += root->val;vec.push_back(root);if (curSum == sum) {res++;}int tmp = curSum;for (int i = 0; i < vec.size() - 1; i++) {tmp -= vec[i]->val;if (tmp == sum) {res++;}}pathSumCore(root->left, sum, curSum, res, vec);pathSumCore(root->right, sum, curSum, res, vec);vec.pop_back();}int pathSum(TreeNode* root, int sum) {if (!root) {return 0;}int curSum = 0;int res = 0;vector<TreeNode*> vec;pathSumCore(root, sum, curSum, res, vec);return res;}
这里注意需要把vec声明为&引用,否则每次都复制一遍vector,效率太低。如下图:
方法二:
我们用一个哈希表来记录扫描过的节点权值和(key),对应的次数(value)。这样做非常巧,比如在序列x1->x2->x3->x4,有x1~x4四个元素和等于sum,由于我们初始化哈希表m为:m[0]=1,则当我们访问到x4,执行res=m[cur_sum-sum]时,cur_sum=sum,所以res=m[cur_sum-sum]=m[0]=1,我们便得到了x1~x4的权值和等于sum。然后执行res[cur_sum]++,意思是把当前和x1~x4的权值和的次数加1。
如果只有x3~x4两个元素的权值和相加等于sum,那这个寻找过程是怎么的呢?
第一次:res=m[cur_sum-sum]=m[x1-sum],然后m[x1]++
第二次:res=m[cur_sum-sum]=m[x1+x2-sum],然后m[x1+x2]++
第三次:res=m[cur_sum-sum]=m[x1+x2+x3-sum],然后m[x1+x2+x3]++
第四次:res=m[cur_sum-sum]=m[x1+x2+x3+x4-sum],然后m[x1+x2]++
因为sum=x3+x4,所以第四次简化为:res=m[cur_sum-sum]=m[x1+x2+x3+x4-sum]=m[x1+x2+x3+x4-(x3+x4)]=m[x1+x2],发现m[x1+x2]在第二次已经存过了,对应的value为1,然后遍历子节点res+=(左子节点res+右子节点res)即可。
int pathSumCore(TreeNode* root, int sum, int curSum, int res, map<int, int> &m) {if (!root) {return 0;}curSum += root->val;res = m[curSum - sum];m[curSum]++;res += pathSumCore(root->left, sum, curSum,res, m) + pathSumCore(root->right, sum, curSum,res, m);m[curSum]--;return res;}int pathSum(TreeNode* root, int sum) {if (!root) {return 0;}int curSum = 0;int res = 0;map<int,int> m;m[0] = 1;return pathSumCore(root, sum, curSum, res, m);;}
方法三:
方法三相当巧妙,直接对每个节点都当成根节点和非根节点来考虑就行了(我一开始也是这么想的,为什么没写出来。。。):
int pathSumCore(TreeNode* root, int sum, int curSum) {if (!root) {return 0;}curSum += root->val;return (curSum==sum)+pathSumCore(root->left, sum, curSum)+ pathSumCore(root->right, sum, curSum);}int pathSum(TreeNode* root, int sum) {if (!root) {return 0;}int curSum = 0;return pathSumCore(root, sum,curSum)+ pathSum(root->left,sum)+ pathSum(root->right, sum);}
更多推荐
Path Sum路径总和系列总结 leetcode
发布评论