溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

LeetCode如何實(shí)現(xiàn)路徑總和

發(fā)布時(shí)間:2021-12-15 09:20:57 來(lái)源:億速云 閱讀:102 作者:小新 欄目:大數(shù)據(jù)

小編給大家分享一下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è)資訊頻道!

向AI問(wèn)一下細(xì)節(jié)

免責(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)容。

AI