您好,登錄后才能下訂單哦!
小編給大家分享一下LeetCode如何實(shí)現(xiàn)路徑總和,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
給定一個(gè)二叉樹和一個(gè)目標(biāo)和,判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑,這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例: 給定如下二叉樹,以及目標(biāo)和 sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回 true
, 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2
。
標(biāo)簽:深度優(yōu)先遍歷
遞歸終止條件:
當(dāng)前節(jié)點(diǎn)為null時(shí)返回false
當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí) 且 路徑和等于目標(biāo)和 則返回true
遞歸過(guò)程:不斷判斷判斷左右子樹
注意點(diǎn):這里涉及到短路問(wèn)題,也就是當(dāng)發(fā)現(xiàn)了某一條路徑和滿足條件時(shí),就應(yīng)該結(jié)束遞歸,故而下面的解法中使用了或
運(yùn)算,這樣不用判斷全部路徑,有滿足條件則結(jié)束,減少時(shí)間復(fù)雜度
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null ) return false; if(root.left == null && root.right == null && sum == root.val) return true; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}
以上是“LeetCode如何實(shí)現(xiàn)路徑總和”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。