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

lylwyy2016 發布于2019-08-26 13:44 / 1073人閱讀

摘要：小鹿題目路徑總和給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。說明葉子節點是指沒有子節點的節點。

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.

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。

說明: 葉子節點是指沒有子節點的節點。

示例:
給定如下二叉樹，以及目標和 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:

▉ 問題分析

1）搜索從根節點到葉子節點能夠達到目標值，毋庸置疑，一看到檢索二叉搜索樹，就應該想起遞歸。

2）第一個想法就是一個個進行相加，將每條路徑相加完成之后，判斷是否達到當前目標值？

3）但是（2）的解決方案的想法要用到遞歸上，需要轉變一下思路，畢竟我們要用遞歸的編程技巧來解決，所以思維需要稍微轉變一下（將問題化成子問題，子問題與總問題有相同的解決思路）。

▉ 算法思路

1）既然要用到遞歸來解決，這樣來想，每遍歷一個結點，我們就用 sum 減去當前結點，然后問題就會變成從當前結點到葉子節點能夠滿足 sum 減去當前結點的值，那么就存在滿足條件的路徑。

2）在（1）中，將問題化成子問題，然后子問題和問題有相同的解決思路，那么就可以使用遞歸來解決。

3）用 flag 做標識，一旦滿足路徑之和等于目標值，就讓改變 flag 的狀態。

▉ 代碼實現

 var hasPathSum = function(root, sum) {
     let flag = false;
     // 判斷當前二叉樹是否等于 null
     if(root == null) return false;

     dfs = (root,sum)=>{
         // 如果當前結點為 null ，返回 false
         if(root == null) return false;
         // 判斷左右子樹是否為 null
         if(root.left == null && root.right == null){
             // 如果不為 null，就判斷當前的值和最后一個結點值是否相同
             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 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學編程的故事。

云服務器 GPU云服務器 javascript算法題匯編語言程序設計第二版課后題答案 javascript必問面試題 javascript權威指南第六版

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/109400.html

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

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 之 JavaScript 解答第104題 —— 二叉樹的最大深度

摘要：小鹿題目二叉樹的最大深度給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿題目：Maximum Depth of Binary Tre...

boredream 2019-08-23 17:07 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 之 JavaScript 解答第142題 —— 環形鏈表 II（Linked Li

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環鏈表的位置。首先，先判斷該單鏈表是否存在循環鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿題目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 評論0 收藏0