劍指offer-二叉樹中和為某一值的路徑 Java

題目要求:
這個題目說的是畴栖,給你一棵二叉樹和一個整數(shù)分俯,你要判斷這棵二叉樹上是否存在一條從根到葉子節(jié)點的路徑茅特,這條路徑上所有節(jié)點中的數(shù)字相加等于給你的整數(shù)。

比如說爵川,給你的二叉樹是:
1
/
2 4
/
8 16
給你的整數(shù)是 13敷鸦。在這棵二叉樹中存在一條從根到葉子節(jié)點的路徑 1->4->8,路徑上的數(shù)字加起來等于 13,于是要返回 true扒披。
思路:
二叉樹的問題 都可以用遞歸的方式去做值依,遍歷左子樹和右子樹
主要是邊界條件的判斷, 這里要求根到葉子結(jié)點的路徑碟案, 那么最后左右結(jié)點一定為空愿险,
sum之和 可以變成一路子上減掉當(dāng)前結(jié)點的值
遞歸的代碼量只有三行,比較簡單价说,方法如下:
public boolean hasSumRecursive(TreeNode root,int sum){
if(root==null) return false;
if(root.leftnode==null &&root.rightnode==null) return sum==root.val;
return hasSumRecursive(root.leftnode,sum-root.val) ||
hasSumRecursive(root.rightnode,sum-root.val);
}
所以采用第二種方式 迭代的方式一步一步來寫
而二叉樹的迭代方法一般都是用一個棧來存儲數(shù)據(jù)以方便記錄路徑
總結(jié)起來如下:
1辆亏、如果只有根節(jié)點或者找到葉子節(jié)點,我們就把其對應(yīng)的val值返回
2鳖目、如果不是葉子節(jié)點扮叨,我們分別對根節(jié)點的左子樹、右子樹進行遞歸领迈,直到找到葉子結(jié)點彻磁。然后遍歷把葉子結(jié)點和父節(jié)點對應(yīng)的val組成的序列返回上一層;
代碼

import java.util.Stack;

public class PathSum62 {
public class TreeNode{
int val;
TreeNode leftnode;
TreeNode rightnode;
TreeNode(int x){
val=x;
}
}
public boolean hasPathSum(TreeNode root,int sum){
if(root==null){
return false;
}
Stack<TreeNode> stack=new Stack<>();
Stack<Integer> num=new Stack<>();
stack.push(root);
num.push(sum);
while (!stack.isEmpty()){
TreeNode n=stack.pop();
int s=num.pop();
if(n.leftnode==null &&n.rightnode==null&&n.val==s) return true;
if(n.leftnode!=null){
stack.push(n.leftnode);
num.push(s-n.val);
}
if(n.rightnode!=null){
stack.push(n.rightnode);
num.push(s-n.val);
}
}
return false;
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末狸捅,一起剝皮案震驚了整個濱河市衷蜓,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌尘喝,老刑警劉巖磁浇,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異瞧省,居然都是意外死亡扯夭,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門鞍匾,熙熙樓的掌柜王于貴愁眉苦臉地迎上來交洗,“玉大人,你說我怎么就攤上這事橡淑」谷” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵梁棠,是天一觀的道長置森。 經(jīng)常有香客問我,道長符糊,這世上最難降的妖魔是什么凫海? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮男娄,結(jié)果婚禮上行贪,老公的妹妹穿的比我還像新娘漾稀。我一直安慰自己,他們只是感情好建瘫,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布崭捍。 她就那樣靜靜地躺著,像睡著了一般啰脚。 火紅的嫁衣襯著肌膚如雪殷蛇。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天橄浓,我揣著相機與錄音粒梦,去河邊找鬼。 笑死贮配,一個胖子當(dāng)著我的面吹牛谍倦,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播泪勒,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼昼蛀,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了圆存?” 一聲冷哼從身側(cè)響起叼旋,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎沦辙,沒想到半個月后夫植,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡油讯,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年详民,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片陌兑。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡沈跨,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出兔综,到底是詐尸還是另有隱情饿凛,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布软驰,位于F島的核電站涧窒,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏锭亏。R本人自食惡果不足惜纠吴,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望慧瘤。 院中可真熱鬧呜象,春花似錦膳凝、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽上煤。三九已至休玩,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間劫狠,已是汗流浹背拴疤。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留独泞,地道東北人呐矾。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像懦砂,于是被迫代替她去往敵國和親蜒犯。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 姓名: 李小娜 [嵌牛導(dǎo)讀] :這篇文章主要介紹了Java二叉排序樹荞膘,包括二叉排序樹的定義罚随、二叉排序樹的性質(zhì)、二叉...
    n184閱讀 631評論 0 0
  • 目錄 1. 棧和隊列1.用兩個隊列實現(xiàn)棧2.用兩個棧實現(xiàn)隊列3.實現(xiàn)一個棧羽资,可以用常數(shù)級時間找出棧中的最小值4.判...
    MigrationUK閱讀 3,040評論 4 20
  • 晚上在看彭小六的簡書文章淘菩,翻到一篇文章,里面介紹了一個好的讀書沉淀方法屠升。 我平時讀書感覺讀完后跟沒讀一樣潮改,沒什么印...
    蝸牛樂讀閱讀 285評論 0 1
  • 還記得小時候?qū)Π职謰寢屨f:“我永遠不學(xué)自行車,寧愿走腹暖』阍冢”后來在初中時學(xué)會了,感覺比走路快多了微服。 看電視被爸爸媽媽碎...
    AnnaFan閱讀 221評論 1 0
  • 文/紫月 輕風(fēng)吹吹舞袖間趾疚, 落花漫漫天際邊, 詩情語意在眼前以蕴, 晨陽隱隱去亦遠糙麦。 尋你,是夢中的思念丛肮, 你時常在夢...
    木夏半年閱讀 363評論 7 30