題目描述
給定一個(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命满，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2。
解題思路
遞歸搜索
代碼實(shí)現(xiàn)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
if(root == null) {
return false;
}
// 判斷是否已經(jīng)走到頭
if(root.left == null && root.right == null) {
return sum == root.val;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
};
