快捷導(dǎo)航

LeetCode -- Path Sum III分析及實(shí)現(xiàn)方法

更新時(shí)間：2017年10月25日 14:32:22 投稿：lqh

這篇文章主要介紹了LeetCode -- Path Sum III分析及實(shí)現(xiàn)方法的相關(guān)資料,希望通過本文能幫助到大家，需要的朋友可以參考下

LeetCode -- Path Sum III分析及實(shí)現(xiàn)方法

題目描述：

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.

給定一個(gè)二叉樹，遍歷過程中收集所有可能路徑的和，找出和等于X的路徑樹。

思路：

設(shè)當(dāng)前節(jié)點(diǎn)為root,分別收集左右節(jié)點(diǎn)路徑和的集合，merge到當(dāng)前集合中；

將當(dāng)前節(jié)點(diǎn)添加到數(shù)組中，構(gòu)成新的可能路徑。

實(shí)現(xiàn)代碼：

/** 
 * 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); 
 } 
}

如有疑問請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章:

相關(guān)文章

Spring MVC整合FreeMarker的示例
這篇文章主要介紹了Spring MVC整合FreeMarker的示例，幫助大家更好的理解和使用Spring MVC，感興趣的朋友可以了解下
2020-12-12
Java8 自定義CompletableFuture的原理解析
這篇文章主要介紹了Java8 自定義CompletableFuture的原理解析，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2021-11-11
Java中去除字符串中所有空格的幾種方法
這篇文章介紹了Java中去除字符串中所有空格的幾種方法，有需要的朋友可以參考一下
2013-07-07
找出鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)元素的二個(gè)方法
本文提供了找出鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)元素的二個(gè)方法，其中一個(gè)方法是JAVA代碼實(shí)現(xiàn)
2013-11-11
Token安全存儲(chǔ)的幾種方式小結(jié)
在現(xiàn)代 Web 應(yīng)用中,身份認(rèn)證與授權(quán)是確保系統(tǒng)安全性的重要部分,Token被廣泛應(yīng)用,作為實(shí)現(xiàn)身份認(rèn)證的主要方式,然而,如何安全地存儲(chǔ)這些 Token,是每個(gè)開發(fā)者在構(gòu)建前端應(yīng)用時(shí)必須考慮的問題,本文將深入探討Token安全存儲(chǔ)的幾種方式,需要的朋友可以參考下
2025-04-04
Java對(duì)時(shí)間的簡(jiǎn)單操作實(shí)例
這篇文章主要介紹了Java對(duì)時(shí)間的簡(jiǎn)單操作,實(shí)例分析了針對(duì)java.util.Date的各類常見操作,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
2015-01-01
Java日期毫秒值和常見日期時(shí)間格式相互轉(zhuǎn)換方法
這篇文章主要給大家介紹了關(guān)于Java日期毫秒值和常見日期時(shí)間格式相互轉(zhuǎn)換的相關(guān)資料,在Java的日常開發(fā)中,會(huì)隨時(shí)遇到需要對(duì)時(shí)間處理的情況,文中給出了詳細(xì)的示例代碼,需要的朋友可以參考下
2023-07-07
Java的基本數(shù)據(jù)類型和運(yùn)算方法(必看篇)
下面小編就為大家?guī)硪黄狫ava的基本數(shù)據(jù)類型和運(yùn)算方法(必看篇)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2017-07-07
SpringBoot集成Redis使用Cache緩存的實(shí)現(xiàn)方法
SpringBoot通過配置RedisConfig類和使用Cache注解可以輕松集成Redis實(shí)現(xiàn)緩存,主要包括@EnableCaching開啟緩存,自定義key生成器,改變序列化規(guī)則,以及配置RedisCacheManager,本文為使用SpringBoot與Redis處理緩存提供了詳實(shí)的指導(dǎo)和示例,感興趣的朋友一起看看吧
2024-10-10
Spring框架中@PostConstruct注解詳解
在Spring項(xiàng)目經(jīng)常遇到@PostConstruct注解,下面這篇文章主要給大家介紹了關(guān)于Spring框架中@PostConstruct注解的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
2022-07-07