LeetCode -- Path Sum III分析及实现方法

LeetCode -- Path Sum III分析及实现方法

题目描述：

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

给定一个二叉树，遍历过程中收集所有可能路径的和，找出和等于X的路径树。

思路：

设当前节点为root,分别收集左右节点路径和的集合，merge到当前集合中；

将当前节点添加到数组中，构成新的可能路径。

实现代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int x) { val = x; }
 * }
 */
public class Solution { 

 private int _sum;
 private int _count;
 public int PathSum(TreeNode root, int sum)
 {
 _count = 0;
 _sum = sum;
 Travel(root, new List<int>());
 return _count;
 } 

 private void Travel(TreeNode current, List<int> ret){
 if(current == null){
  return ;
 } 

 if(current.val == _sum){
  _count ++;
 } 

 var left = new List<int>();
 Travel(current.left, left); 

 var right = new List<int>();
 Travel(current.right, right); 

 ret.AddRange(left);
 ret.AddRange(right); 

 for(var i = 0;i < ret.Count; i++){
  ret[i] += current.val;
  if(ret[i] == _sum){
  _count ++;
  }
 }
 ret.Add(current.val); 

 //Console.WriteLine(ret);
 }
}

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • laravel源码分析队列Queue方法示例

    目录 前言 队列任务的创建 队列任务的分发 前言 队列 (Queue) 是 laravel 中比较常用的一个功能,队列的目的是将耗时的任务延时处理,比如发送邮件,从而大幅度缩短 Web 请求和响应的时间.本文我们就来分析下队列创建和执行的源码. 队列任务的创建 先通过命令创建一个 Job 类,成功之后会创建如下文件 laravel-src/laravel/app/Jobs/DemoJob.php. > php artisan make:job DemoJob > Job created suc

  • 浅谈web上存漏洞及原理分析、防范方法（文件名检测漏洞）

    我们通过前篇:<浅谈web上存漏洞及原理分析.防范方法(安全文件上存方法)>,已经知道后端获取服务器变量,很多来自客户端传入的.跟普通的get,post没有什么不同.下面我们看看,常见出现漏洞代码.1.检测文件类型,并且用用户上存文件名保存 复制代码 代码如下: if(isset($_FILES['img'])){    $file = save_file($_FILES['img']); if($file===false) exit('上存失败!'); echo "上存成功!&qu

  • PHP Header失效的原因分析及解决方法

    在PHP中用header("location:test.php")进行跳转要注意以下几点: 1.location和":"号间不能有空格,否则会出错. 2.在用header前不能有任何的输出,包括include的页面中标签"?>"后不能有空格!! 3.header后的PHP代码还会被执行. 续: 问题:header函数前输入内容 一般来说在header函数前不能输出html内容,类似的还有setcookie() 和 session 函数,这些

  • python使用htmllib分析网页内容的方法

    本文实例讲述了python使用htmllib分析网页内容的方法.分享给大家供大家参考.具体实现方法如下: import htmllib, urllib, formatter, sys website = urllib.urlopen("http://yourweb.com") data = website.read() website.close() format = formatter.AbstractFormatter(formatter.DumbWriter(sys.stdout

  • Android Force Close 出现的异常原因分析及解决方法

    一.原因: forceclose,意为强行关闭,当前应用程序发生了冲突. NullPointExection(空指针),IndexOutOfBoundsException(下标越界),就连Android API使用的顺序错误也可能导致(比如setContentView()之前进行了findViewById()操作)等等一系列未捕获异常 二.如何避免 如何避免弹出Force Close窗口 ,可以实现Thread.UncaughtExceptionHandler接口的uncaughtExcepti

  • MySQL 出现错误1418 的原因分析及解决方法

    MySQL 出现错误1418 的原因分析及解决方法 具体错误: 使用mysql创建.调用存储过程,函数以及触发器的时候会有错误符号为1418错误. ERROR 1418 (HY000): This function has none of DETERMINISTIC, NO SQL,or READS SQL DATA in its declaration and binary logging is enabled(you *might* want to use the less safe log

  • PHP抓取及分析网页的方法详解

    本文实例讲述了PHP抓取及分析网页的方法.分享给大家供大家参考,具体如下: 抓取和分析一个文件是非常简单的事.这个教程将通过一个例子带领你一步一步地去实现它.让我们开始吧! 首先,我首必须决定我们将抓取的URL地址.可以通过在脚本中设定或通过$QUERY_STRING传递.为了简单起见,让我们将变量直接设在脚本中. <?php $url = 'http://www.php.net'; ?> 第二步,我们抓取指定文件,并且通过file()函数将它存在一个数组里. <?php $url =

  • Ajax向后台传json格式的数据出现415错误的原因分析及解决方法

    Ajax向后台传json格式的数据出现415错误的原因分析及解决方法

    问题描述: ajax往后台传json格式数据报415错误,如下图所示 页面代码 function saveUser(){ var uuId = document.getElementById("uuid").value; var idCard = document.getElementById("idCard").value; alert(uuId+idCard); // var result = new Object(); // result.uuId = uuI

  • 腾讯云ubuntu服务器tomcat访问慢的原因分析及解决方法

    在腾讯云上配了个一元的学生云,开始一切正常,直到配置tomcat开始出现各种莫名其妙的问题.最莫名其妙的是tomcat启动了,端口也 正常监听,安全组也放行端口了,然后问题来了. 用浏览器访问tomcat主页,会发现超级慢,浏览器一直在等待服务器的响应,从这里可以看出能够接入8080端口,但是服务器没有返回数据.(这个问题折腾几天) 后来在网上找了无数资料,终于发现了原因.tomcat8.0在腾讯云ubuntu14.04上有bug. 问题原因: 随机数引起线程阻塞. tomcat不断启动,关闭,

随机推荐