[[426794]]

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn。轉載本文請聯系三分鐘學前端公眾號。

關于樹基礎看這里：適合初學者的樹

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

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

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

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

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

解題思路：

只需要遍歷整棵樹

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

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

代碼實現：

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

解題思路：

只需要遍歷整棵樹

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

代碼實現：

var hasPathSum = function(root, sum) { 
  // 根節點為空 
  if (root === null) return false; 
   
  // 葉節點 同時 sum 參數等于葉節點值 
  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/