1.题目
-
难度:简单
-
涉及知识:树、广度优先搜索
-
题目:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
-
说明:叶子节点是指没有子节点的节点。
-
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
2.解题:
/**
* 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){
return false;
}
sum = sum - root.val;
if(!root.left && !root.right){
return sum === 0;
}
//如果还有子节点,则继续递归遍历该节点的孩子
return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
};
- LeetCode Submit
执行用时 :92 ms, 在所有 JavaScript 提交中击败了89.42%的用户
内存消耗 :37.1 MB, 在所有 JavaScript 提交中击败了51.15%的用户
3.解析
- 递归方式
同前面二叉树遍历方式,总体采用递归方式进行。
- 正向思路 和 反向思路
kk一开始的思路是采用正面的思路,即输入固定的sum值22,遍历每条路径取得总和,与sum进行比对,后来发现这样的做法性能并不高
改用反向思路,即从sum开始处理,每遍历一项,就从sum当中减去相应的该节点的值,如果减到最后(没有left,right节点)的情况,sum若为0即视为该二叉树存在该路径总和。
有方法优化请各位多多指教!