学网站建设需要几年,财务软件排名,我们的网站正在建设之中,北京学电脑的培训机构原题链接#xff1a;113.路径总和II 需复刷
思路#xff1a; 跟112.路径总和不同#xff0c;该题是要你找出所有相同的路径#xff0c;那么此时就要注意存储#xff0c;递归和回溯了。
全代码#xff1a;
class Solution {
public:vectorvectorint re…原题链接113.路径总和II 需复刷
思路 跟112.路径总和不同该题是要你找出所有相同的路径那么此时就要注意存储递归和回溯了。
全代码
class Solution {
public:vectorvectorint result;vectorint path;// 递归函数不需要返回值因为我们要遍历整个树void traversal(TreeNode* cur, int count) {if (!cur-left !cur-right count 0) { // 遇到了叶子节点且找到了和为sum的路径result.push_back(path);return;}if (!cur-left !cur-right) return ; // 遇到叶子节点而没有找到合适的边直接返回if (cur-left) { // 左 空节点不遍历path.push_back(cur-left-val);count - cur-left-val;traversal(cur-left, count); // 递归count cur-left-val; // 回溯path.pop_back(); // 回溯}if (cur-right) { // 右 空节点不遍历path.push_back(cur-right-val);count - cur-right-val;traversal(cur-right, count); // 递归count cur-right-val; // 回溯path.pop_back(); // 回溯}return ;}vectorvectorint pathSum(TreeNode* root, int targetSum) {result.clear();path.clear();if (root NULL) return result;path.push_back(root-val); // 把根节点放进路径traversal(root, targetSum - root-val);return result;}
};
