leetcode113路径总和2

简介: leetcode113路径总和2
113. 路径总和 II

题目描述:

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

题解思路:

利用回溯来遍历每一种情况,找到符合题目要求的路径,添加进vector<vector>中。

定义一个全局的vector<vector> result来存放结果

定义一个全局的vector every来存放符合条件的路径

  • 这个符合条件可以利用acommulate来对every进行求和,如果求和结果等于给定的条件则将该路径加入到result中
  • 部分代码:
if(accumulate(every.begin(),every.end(),0) == count) result.push_back(every);

递归三件套

  • 参数和返回值
  • 根节点和targetSum,targetSum用来判断某路径是否符合要求,需要访问整棵树才可以得出结果,不需要像leetcode112路径总和1那样找到了符合的就返回,所以这道题不需要返回值,只需要通过它来改变全局变量resul即可
  • 终止条件
  • 当访问的是叶子节点的时候,来判断该路径是否符合条件
  • 本层逻辑
  • 回溯就在这个地方
  • 部分代码:
if(root->left){
            every.push_back(root->left->val);  //回溯
            backTracking(root->left,count);
            every.pop_back();  //回溯
        }    
        //右
        if(root->right){
            every.push_back(root->right->val);  //回溯
            backTracking(root->right,count);
            every.pop_back();  //回溯
        }

完整代码:

class Solution {
public:
    vector<vector<int>> result;
    vector<int> every;
    void backTracking(TreeNode * root, int count){
        if(!root->left && !root->right){
            if(accumulate(every.begin(),every.end(),0) == count) result.push_back(every);
            return;
        }
        //左
        if(root->left){
            every.push_back(root->left->val);
            backTracking(root->left,count);
            every.pop_back();
        }    
        //右
        if(root->right){
            every.push_back(root->right->val);
            backTracking(root->right,count);
            every.pop_back();
        }    
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        result.clear();
        every.clear();
        if(!root) return result;
        every.push_back(root->val);
        backTracking(root, targetSum);
        return result;
    }
};


相关文章
|
1月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
23 0
|
4月前
|
算法 Unix 测试技术
力扣经典150题第五十二题:简化路径
力扣经典150题第五十二题:简化路径
42 0
|
1月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
27 0
|
3月前
|
机器人 Python
【Leetcode刷题Python】62. 不同路径
LeetCode 62题 "不同路径" 的Python解决方案,使用动态规划算法计算机器人从网格左上角到右下角的所有可能路径数量。
68 0
|
5月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
3月前
|
Python
【Leetcode刷题Python】113. 路径总和 II
LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
41 3
【Leetcode刷题Python】113. 路径总和 II
|
3月前
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
32 1
【Leetcode刷题Python】64. 最小路径和
|
3月前
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
|
3月前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和