路徑總和

題目描述：給你二叉樹的根節(jié)點 root 和一個表示目標和的整數(shù) targetSum ，判斷該樹中是否存在 根節(jié)點到葉子節(jié)點 的路徑，這條路徑上所有節(jié)點值相加等于目標和 targetSum 。

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

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/path-sum/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸

首先，如果root為null，直接返回false。

否則，調(diào)用遞歸方法hasPathSum(TreeNode root, int targetSum, int curSum)，root為當前節(jié)點，targetSum為目標和，curSum當前路徑上的累加和，遞歸過程如下：

• 如果root為null，直接返回；

• 否則，curSum累加當前節(jié)點的值；

• 然后判斷如果root的左子樹或者右子樹有一邊為null，則調(diào)用遞歸方法，參數(shù)為不為null的子樹和curSum，然后返回；

• 如果root的左子樹和右子樹都不為null，則左右子樹都要調(diào)用遞歸方法。

過程中當?shù)竭_子節(jié)點時需要判斷當前路徑的和curSum和targetSum是否相等，如果相等，則將result更新為true，最后返回result。

說明：該題的解法過程和 LeetCode-111-二叉樹的最小深度 完全一樣。

【每日寄語】 收集每一個快樂的瞬間，用它來回擊每一個糟糕的日子。