C#LeetCode刷题之#112-路径总和(Path Sum)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4078 访问。
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4078 访问。
public class Program {
public static void Main(string[] args) {
var root = new TreeNode(1) {
left = new TreeNode(2) {
right = new TreeNode(5)
},
right = new TreeNode(3)
};
var res = HasPathSum(root, 4);
Console.WriteLine(res);
res = HasPathSum2(root, 5);
Console.WriteLine(res);
Console.ReadKey();
}
public static bool HasPathSum(TreeNode root, int sum) {
if(root == null) return false;
var res = false;
PathSum(root, root.val, sum, ref res);
return res;
}
public static void PathSum(TreeNode root, int cursum, int sum, ref bool has) {
if(root.left == null && root.right == null && cursum == sum) {
//若左右子节点都为空,本次路径结束
has = true;
return;
}
if(root.left != null)
//若左子节点不为空,则将左子节点和当前和累加之后参与下次递归
PathSum(root.left, cursum + root.left.val, sum, ref has);
if(root.right != null)
//若右子节点不为空,则将右子节点和当前和累加之后参与下次递归
PathSum(root.right, cursum + root.right.val, sum, ref has);
}
public static bool HasPathSum2(TreeNode root, int sum) {
//边界判定
if(root == null) return false;
//如果 sum 等于当前节点的值,并且为叶子节点时,返回 true
if(root.val == sum && root.left == null && root.right == null) return true;
//每次传递时用 sum - 当前值
return HasPathSum2(root.left, sum - root.val) ||
HasPathSum2(root.right, sum - root.val);
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
}
以上给出2种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4078 访问。
True
False
分析:
显而易见,以上2种算法的时间复杂度均为: 。
最新文章
- SVN图形管理工具-Submint
- Haskell 参考资料
- JS-节点属性(常用!)
- Mysql新知识点150928
- windows环境下 svn 客户端
- ios layoutsubView 何时被调用
- bash 中的case语法
- 【HDOJ】2268 How To Use The Car
- [Swust OJ 767]--将军回家(Dijkstra算法)
- bzoj2982: combination(lucas定理板子)
- 选做题:设计并实现一个Book类
- Nginx的进程模型及高可用方案(OpenResty)
- Win7或Win8上安装VS2015报“安装包丢失或损坏”问题的解决办法
- springboot+thymeleaf刨坑——首页加载js/css等失败解决方法
- 第三章 列表(d)选择排序
- Asp.net MVC检测到有潜在危险的 Request.Form 值
- Web自动化 - 选择操作元素 2
- Android DiskLruCache完全解析,硬盘缓存的最佳方案
- JDBC上关于数据库中多表操作一对多关系和多对多关系的实现方法
- jquery ajaxSubmit