路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
递归：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) {
return false;
}
if(root.left == null && root.right==null) {
return targetSum == root.val;
}
boolean left = hasPathSum(root.left, targetSum-root.val);
boolean right = hasPathSum(root.right, targetSum-root.val);
return left||right;
}
}
迭代
思路，
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) {
return false;
}
Queue<TreeNode> queueNode = new LinkedList();
Queue<Integer> queueSum = new LinkedList();
queueNode.add(root);
queueSum.add(root.val);
while(!queueNode.isEmpty()) {
root = queueNode.poll();
int sum = queueSum.poll();
if(root.left == null && root.right == null ) {
if(sum == targetSum) {
return true;
}
continue;
}
if(root.left != null) {
queueNode.add(root.left);
queueSum.add(sum+root.left.val);
}
if(root.right != null) {
queueNode.add(root.right);
queueSum.add(sum+root.right.val);
}
}
return false;
}
}
