Leetcode No.113 路径总和 II
2023-03-20 14:56:07 时间
一、题目描述
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]]
示例 2: 输入:root = [1,2,3], targetSum = 5 输出:[]
示例 3: 输入:root = [1,2], targetSum = 0 输出:[]
提示:
树中节点总数在范围 [0, 5000] 内 -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000
二、题目描述
注意到本题的要求是,找到所有满足从「根节点」到某个「叶子节点」经过的路径上的节点之和等于目标和的路径。核心思想是对树进行一次遍历,在遍历时记录从根节点到当前节点的路径和,以防止重复计算。
我们可以采用深度优先搜索的方式,枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点,且此时路径和恰为目标和时,我们就找到了一条满足条件的路径。
三、代码
class Solution {
public:
vector<vector<int>> rs;
vector<int> vec;
vector<vector<int>> pathSum(TreeNode* root,int targetSum) {
dfs(root,0,targetSum);
return rs;
}
void dfs(TreeNode* root, int sum,int targetSum){
if(root==nullptr){
return;
}
vec.push_back(root->val);
sum+=root->val;
if(root->left==nullptr && root->right==nullptr && targetSum==sum){
rs.push_back(vec);
}
dfs(root->left,sum,targetSum);
dfs(root->right,sum,targetSum);
vec.pop_back();
}
};
四、复杂度分析
时间复杂度:O(N^2),其中 N 是树的节点数。在最坏情况下,树的上半部分为链状,下半部分为完全二叉树,并且从根节点到每一个叶子节点的路径都符合题目要求。此时,路径的数目为 O(N),并且每一条路径的节点个数也为 O(N),因此要将这些路径全部添加进答案中,时间复杂度为 O(N^2)。
空间复杂度:O(N),其中 N是树的节点数。空间复杂度主要取决于栈空间的开销,栈中的元素个数不会超过树的节点数。
相关文章
- Linux 上的六大安卓模拟器
- 7个改变我生活的Git小技巧
- 苹果 iOS/iPadOS 15、macOS 12、watchOS 8 公测版 Beta 4 更新发布
- HarmonyOS《鸿蒙操作系统开发入门经典》|线程管理|剪贴板
- 服务器该选择Windows系统还是Linux系统?
- Windows 10总强制更新?教你简单4步彻底关闭!几分钟就能搞定
- 谈一谈Windows中的堆
- 因为 Windows 原生不好用,我给你找了这些第三方软件
- Windows 11将沿用Windows 10升级模式 并会有LTSC版本
- 再无Semi-Annual频道:自Windows Server 2022开始只有LTSC版本
- 微软:Windows 11 将遵循 Windows 10 的更新模式,依然有 LTSC 版本
- Windows 10各版本占比:20H2成最稳定选择 近4成用户选择
- VzLinux是你从未听说过的基于RHEL的Linux操作系统
- 常用插件:分享12款超级好用的 Chrome 插件
- Windows原生不好用,我给你找了这些第三方软件
- 外媒总结 Windows 11 家庭版、专业版区别:专业版可支持 2TB 内存
- Windows 11家庭版、专业版区别曝光:功能差异不小
- Windows 10专业版,怎么隐藏任务栏u盘图标?Windows 10隐藏U盘图标方法
- Windows 10更新,提示缺少重要的安全和质量修复怎么办?
- 想要升级Windows11系统?请注意这些问题