成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

LeetCode 之 JavaScript 解答第112題 —— 路徑總和（Path Sum）

lylwyy2016 / 1140人閱讀

摘要：小鹿題目路徑總和給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，判斷該樹(shù)中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。說(shuō)明葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

Time：2019/4/26
Title: Path Sum
Difficulty: Easy
Author: 小鹿

題目：Path Sum（路徑總和）

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，判斷該樹(shù)中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。


示例: 
給定如下二叉樹(shù)，以及目標(biāo)和 sum = 22，

Example:

Given the below binary tree and sum = 22,

      5
     / 
    4   8
   /   / 
  11  13  4
 /        
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solve:
▉ 問(wèn)題分析
1）搜索從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)能夠達(dá)到目標(biāo)值，毋庸置疑，一看到檢索二叉搜索樹(shù)，就應(yīng)該想起遞歸。
2）第一個(gè)想法就是一個(gè)個(gè)進(jìn)行相加，將每條路徑相加完成之后，判斷是否達(dá)到當(dāng)前目標(biāo)值？


3）但是 （2）的解決方案的想法要用到遞歸上，需要轉(zhuǎn)變一下思路，畢竟我們要用遞歸的編程技巧來(lái)解決，所以思維需要稍微轉(zhuǎn)變一下（將問(wèn)題化成子問(wèn)題，子問(wèn)題與總問(wèn)題有相同的解決思路）。
▉ 算法思路
1）既然要用到遞歸來(lái)解決，這樣來(lái)想，每遍歷一個(gè)結(jié)點(diǎn)，我們就用 sum 減去當(dāng)前結(jié)點(diǎn)，然后問(wèn)題就會(huì)變成從當(dāng)前結(jié)點(diǎn)到葉子節(jié)點(diǎn)能夠滿(mǎn)足 sum 減去當(dāng)前結(jié)點(diǎn)的值，那么就存在滿(mǎn)足條件的路徑。
2）在（1）中，將問(wèn)題化成子問(wèn)題，然后子問(wèn)題和問(wèn)題有相同的解決思路，那么就可以使用遞歸來(lái)解決。


3）用 flag 做標(biāo)識(shí)，一旦滿(mǎn)足路徑之和等于目標(biāo)值，就讓改變 flag 的狀態(tài)。
▉ 代碼實(shí)現(xiàn)
 var hasPathSum = function(root, sum) {
     let flag = false;
     // 判斷當(dāng)前二叉樹(shù)是否等于 null
     if(root == null) return false;

     dfs = (root,sum)=>{
         // 如果當(dāng)前結(jié)點(diǎn)為 null ，返回 false
         if(root == null) return false;
         // 判斷左右子樹(shù)是否為 null
         if(root.left == null && root.right == null){
             // 如果不為 null，就判斷當(dāng)前的值和最后一個(gè)結(jié)點(diǎn)值是否相同
             if(sum == root.val){
                 flag = true;
                 return;
             }
         }
         // 遞歸搜索所有路徑
         dfs(root.left,sum - root.val)
         dfs(root.right,sum - root.val)
     }
     dfs(root,sum)
     return flag;
 };


歡迎一起加入到 LeetCode 開(kāi)源 Github 倉(cāng)庫(kù)，可以向 me 提交您其他語(yǔ)言的代碼。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開(kāi)源小倉(cāng)庫(kù)！
Github：https://github.com/luxiangqia...
歡迎關(guān)注我個(gè)人公眾號(hào)：「一個(gè)不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/109400.html

相關(guān)文章

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...

    tain335 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言?xún)?nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱(chēng)和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第104題 —— 二叉樹(shù)的最大深度

    摘要：小鹿題目二叉樹(shù)的最大深度給定一個(gè)二叉樹(shù)，找出其最大深度。二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。求二叉樹(shù)的深度，必然要用到遞歸來(lái)解決。分別遞歸左右子樹(shù)。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿 題目：Maximum Depth of Binary Tre...

    boredream 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線(xiàn)網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第142題 —— 環(huán)形鏈表 II（Linked Li

    摘要：說(shuō)明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個(gè)快慢指針?lè)謩e指向鏈表的頭部，每次移動(dòng)兩步，每次移動(dòng)一步，移動(dòng)的步數(shù)是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿 題目：Linked List Cycle II Giv...

    whidy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<