leetcode112：路径总和

[sisterAn]

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22 ，

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

返回 true , 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
附赠leetcode地址：leetcode

[7777sea]

var hasPathSum = function(root, sum) {
 
 if (root === null) return false
 if (root.left === null && root.right === null && root.val === sum) return true
 return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)

};

[Malenconiaprincep]

深度遍历

var hasPathSum = function(root, sum) {
 return dfs(root,sum)
};

var dfs = function(root, sum) {
 if(root === null) return false
 if(!root.left && !root.right && root.val === sum) return true
 return dfs(root.left, sum - root.val) || dfs(root.right, sum - root.val)
}

[plane-hjh]

深度优先遍历

/**
 * 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;

 // 只有一个根节点，主要是这里的两个判断
 if (root.left === null && root.right === null && root.val === sum) return true;

 // 把总和减去当前值递归下去
 const left = hasPathSum(root.left, sum - root.val);
 const right = hasPathSum(root.right, sum - root.val);
 return left || right;
};

迭代

/**
 * 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;
 let stack = [root];
 let sumStack = [sum - root.val];
 while (stack.length > 0) {
 let node = stack.pop();
 let curSum = sumStack.pop();
 if (node.left === null && node.right === null && curSum === 0) {
 return true;
 }
 if (node.right !== null) {
 stack.push(node.right);
 sumStack.push(curSum - node.right.val);
 }
 if (node.left !== null) {
 stack.push(node.left);
 sumStack.push(curSum - node.left.val);
 }
 }
 return false;
};

这些都是二叉树遍历的延伸问题

[sisterAn]

解题思路：

只需要遍历整棵树

• 如果当前节点不是叶子节点，递归它的所有子节点，传递的参数就是 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

[GolderBrother]

• 如果根节点为空，直接返回 false
• 如果左节点和右节点都为空，就直接比较根节点值
• 将总和减去当前值得到差值，不断递归来找是否等于这个差值的值，左节点找不到就找右节点

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
 // 根节点为空，直接返回false
 if (root == null) return false;
 // 左节点和右节点都为空，就直接比较根接点值
 if (root.left == null && root.right == null) return root.val === sum;
 // 将总和减去当前值得到差值，不断递归来找是否等于这个差值的值，左节点找不到就找右节点
 sum = sum - root.val;
 return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
};

[AnranS]

var hasPathSum = function(root, sum) {
 let numSum = 0;
 let res = false;
 function help(root) {
 if(!root) return;
 numSum+=root.val;
 help(root.left);
 help(root.right);
 // 走到根节点
 if(!root.left&&!root.right) {
 if(numSum === sum){
 res = true;
 }
 }
 numSum-=root.val;
 }
 help(root);
 return res;
};