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)文章
這篇文章主要介紹了ssm整合shiro使用詳解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
這篇文章主要為大家介紹了AQS同步組件Semaphore信號(hào)量案例剖析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
一篇文章帶你學(xué)會(huì)Spring?MVC表單標(biāo)簽
Spring MVC表單標(biāo)簽是網(wǎng)頁的可配置和可重復(fù)使用的構(gòu)建塊,下面這篇文章主要給大家介紹了如何通過一篇文章學(xué)會(huì)Spring?MVC表單標(biāo)簽的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
java實(shí)現(xiàn)釘釘機(jī)器人消息推送的示例代碼
這篇文章主要介紹了java實(shí)現(xiàn)釘釘機(jī)器人消息推送的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01
SpringFramework應(yīng)用接入Apollo配置中心過程解析
這篇文章主要介紹了SpringFramework應(yīng)用接入Apollo配置中心過程解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了SpringMVC---配置與使用的示例，幫助大家更好的理解和學(xué)習(xí)spring框架，感興趣的朋友可以了解下2020-10-10
SpringBoot原生組件注入實(shí)現(xiàn)兩種方式介紹
SpringBoot是Spring全家桶的成員之一，基于約定優(yōu)于配置的思想（即有約定默認(rèn)值，在不配置的情況下會(huì)使用默認(rèn)值，在配置文件下配置的話會(huì)使用配置的值）。SpringBoot是一種整合Spring技術(shù)棧的方式(或者說是框架)，同時(shí)也是簡化Spring的一種快速開發(fā)的腳手架2022-10-10
Java線程安全的計(jì)數(shù)器簡單實(shí)現(xiàn)代碼示例
這篇文章主要介紹了Java線程安全的計(jì)數(shù)器簡單實(shí)現(xiàn)代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。2017-10-10
Java數(shù)據(jù)結(jié)構(gòu)與算法之稀疏數(shù)組與隊(duì)列深入理解
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)與算法之稀疏數(shù)組與隊(duì)列深入理解，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了java之構(gòu)造器的重載問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-03-03