[[426794]]

本文轉(zhuǎn)載自微信公眾號「三分鐘學前端」，作者sisterAn。轉(zhuǎn)載本文請聯(lián)系三分鐘學前端公眾號。

關(guān)于樹基礎(chǔ)看這里：適合初學者的樹

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

說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例: 給定如下二叉樹，以及目標和 sum = 22 ，

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

返回 true , 因為存在目標和為 22 的根節(jié)點到葉子節(jié)點的路徑 5->4->11->2。

解題思路：

只需要遍歷整棵樹

如果當前節(jié)點不是葉子節(jié)點，遞歸它的所有子節(jié)點，傳遞的參數(shù)就是 sum 減去當前的節(jié)點值;

如果當前節(jié)點是葉子節(jié)點，判斷參數(shù) sum 是否等于當前節(jié)點值，如果相等就返回 true，否則返回 false。

代碼實現(xiàn)：

var hasPathSum = function(root, sum) { 
  // 根節(jié)點為空 
  if (root === null) return false; 
   
  // 葉節(jié)點 同時 sum 參數(shù)等于葉節(jié)點值 
  if (root.left === null && root.right === null) return root.val === sum; 
 
  // 總和減去當前值，并遞歸 
  sum = sum - root.val 
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum); 
}; 

解題思路：

只需要遍歷整棵樹

• 如果當前節(jié)點不是葉子節(jié)點，遞歸它的所有子節(jié)點，傳遞的參數(shù)就是 sum 減去當前的節(jié)點值;
• 如果當前節(jié)點是葉子節(jié)點，判斷參數(shù) sum 是否等于當前節(jié)點值，如果相等就返回 true，否則返回 false。

代碼實現(xiàn)：

var hasPathSum = function(root, sum) { 
  // 根節(jié)點為空 
  if (root === null) return false; 
   
  // 葉節(jié)點 同時 sum 參數(shù)等于葉節(jié)點值 
  if (root.left === null && root.right === null) return root.val === sum; 
 
  // 總和減去當前值，并遞歸 
  sum = sum - root.val 
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum); 
}; 

leetcode：https://leetcode-cn.com/problems/path-sum/solution/javascript-lu-jing-zong-he-by-user7746o/