原题链接:http://oj.leetcode.com/problems/path-sum-ii/这道题是树的题目,跟Path
Sum的要求很接近,都是寻找从根到叶子的路径。这道题目的要求是求所有满足条件的路径,所以我们需要数据结构来维护中间路径结果以及保存满足条件的所有路径。这里的时间复杂度仍然只是一次遍历O(n),而空间复杂度则取决于满足条件的路径和的数量(假设是k条),则空间是O(klogn)。代码如下:public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root==null)
return res;
ArrayList<Integer> item = new ArrayList<Integer>();
item.add(root.val);
helper(root,sum-root.val,item,res);
return res;
}
private void helper(TreeNode root, int sum, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res)
{
if(root == null)
return;
if(root.left==null && root.right==null && sum==0)
{
res.add(new ArrayList<Integer>(item));
return;
}
if(root.left!=null)
{
item.add(root.left.val);
helper(root.left,sum-root.left.val,item,res);
item.remove(item.size()-1);
}
if(root.right!=null)
{
item.add(root.right.val);
helper(root.right,sum-root.right.val,item,res);
item.remove(item.size()-1);
}
}
这类求解树的路径的题目是一种常见题型,类似的有Binary
Tree Maximum Path Sum,那道题更加复杂一些,路径可以起始和结束于任何结点(把二叉树看成无向图),有兴趣的朋友可以看看哈。
分享到:
相关推荐
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Article-Views-II-LeetCode.png 平均工资-部门-VS-公司-LeetCode.png 平均销售价格-LeetCode.png 每台机器平均处理时间 LeetCode.png Bank-Account-Summary-II-LeetCode.png Bank-Account-Summary-LeetCode.png 大国...
cauly-rust-leetcode-utils={path="path/to/cauly-rust-leetcode-utils"} 使用来自 cauly-rust-leetcode-utils 的数据结构(“使用 cauly_rust_leetcode_utils::..”) 运行cargo run --manifest-path=path/to/cauly...
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Swif-LeetCode-Utils:在LeetCode上快速创建和打印ListNode和TreeNode的方式
RandomPickWithWeight-LeetCode-528-源码.rar
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
2sum leetcode leetcode 方法 哈希: 2Sum->3Sum(hash) 2Sum Less Than K->3Sum Closet->3Sum Smaller(两个指针接近) 找到重复的号码 两个指针: 链表循环 BF: DP: 数学: i^0=i;i^i=0 单号->单号2->单号3 n&n...
Java-Leetcode-杨辉三角
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo 中的problems文件夹 使用1.two-sum.js案例导出解决方案 module . exports = { // ignore: true, fn : ...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
Leetcode-解决方案-CSharp ***此存储库将包含 C# 中许多 Leetcode 问题的解决方案 收集雨水 - Leetcode 42 (Hard) 文本对齐 - Leetcode 68(硬) 买卖股票的最佳时机 III - Leetcode 123 (Hard) 买卖股票的最佳时机 ...
leetcode 答案 -leetcode- leetcode刷题指南 不只是答案 更多的是过程 更重要的是纠错的过程
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...