题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true
题目解析
思路一
我们先判断是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum，可以先将每条从根节点到叶子节点路径中所有节点的值都计算出来并存入sum数组，然后判断targetSum是否等于sum数组中的某个值，如果sum中存在等于targetSum的值,说明存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum，否则说明不存在
var hasPathSum = function(root, targetSum) { if(!root) { return false } // 创建一个数组,记录根节点到每个叶子节点的数值之和 const sum = []; // 创建一个数组,用于遍历每条根节点到叶子节点路径中结点数值之和 const rootSum = (root,num) => { if(!root){ sum.push(num); return; } num += root.val; if(!root.left){ rootSum(root.right,num); } else if(!root.right){ rootSum(root.left,num); } else{ rootSum(root.left,num); rootSum(root.right,num); } } // 当左右子树都为空时才是叶子节点 rootSum(root,0); if(sum.indexOf(targetSum) !== -1) return true; return false; };
思路二
// 每次循环取出一个节点，要同时入它的所有子节点 var hasPathSum = function(root, targetSum) { if (!root) return false; const queNode = [root]; const queVal = [root.val]; while (queNode.length) { // 取出当前节点 const curNode = queNode.shift(); const curSum = queVal.shift(); // 判断是否为叶子节点 if (!curNode.left && !curNode.right) { if (curSum === targetSum) return true; } // 当前节点的左节点入队列，当前路径和+左节点的值 入列 if (curNode.left) { queNode.push(curNode.left); queVal.push(curSum + curNode.left.val); } if (curNode.right) { queNode.push(curNode.right); queVal.push(curSum + curNode.right.val); } } return false; };
