递归
解题思路
从根节点递归开始，每当遇到一个节点的时候，从目标值里扣除节点值；
一直到叶子节点判断目标值是否等于 0；
复杂度
-
时间复杂度：
O(N)，其中 N 是树的节点数，对每个节点访问一次； -
空间复杂度：
O(H)，其中 H 是树的高度；- 空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为
O(N)； - 平均情况下树的高度与节点数的对数正相关，空间复杂度为
O(logN)；
- 空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为
代码实现
var hasPathSum = function (root, targetSum) {
if (root === null) return false;
// 叶子节点的时候判断目标值是否为 0
if (root.left === null && root.right === null) return root.val === targetSum;
// 目标值每次减去当前节点值，最后判断目标值是否等于叶子节点的值
let offset = targetSum - root.val;
// 递归判断左右子节点
return hasPathSum(root.left, offset) || hasPathSum(root.right, offset)
};
回溯
图解
复杂度
-
时间复杂度：
O(N)，其中 N 是树的节点数，对每个节点访问一次； -
空间复杂度：
O(H)，其中 H 是树的高度；- 空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为
O(N)； - 平均情况下树的高度与节点数的对数正相关，空间复杂度为
O(logN)；
- 空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为
代码实现
var hasPathSum = function (root, targetSum) {
if (root === null) return false;
return traversal(root, targetSum - root.val);
};
const traversal = (root, targetSum) => {
if (root.left === null && root.right === null) {
return targetSum === 0; // 遇到叶子节点直接返回
}
// 左
if (root.left) {
targetSum -= root.left.val; // 递归，处理节点;
if (traversal(root.left, targetSum)) return true; // 只有遇到叶子节点并且 targetSum===0，才会执行
targetSum += root.left.val; // 回溯，撤销处理结果
}
// 右
if (root.right) {
targetSum -= root.right.val; // 递归，处理节点;
if (traversal(root.right, targetSum)) return true; // 只有遇到叶子节点并且 targetSum===0，才会执行
targetSum += root.right.val; // 回溯，撤销处理结果
}
return false;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
第 4️⃣ 座大山：手写 promise
上一篇
评论
