leetcode 112. 路径总和

一、题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

二、解法

递归：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null) return root.val==targetSum;
        return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
    }
}

迭代：
BFS：用另一个队保存到该节点的路径的总和。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        Queue nodeQueue=new LinkedList<>();
        Queue valQueue=new LinkedList<>();
        nodeQueue.offer(root);
        valQueue.offer(root.val);
        while(!nodeQueue.isEmpty()){
            TreeNode node=nodeQueue.poll();
            int val=valQueue.poll();
            if(node.left==null&&node.right==null){
                if(val==targetSum){
                    return true;
                }
            }else{
                if(node.left!=null){
                    nodeQueue.offer(node.left);
                    valQueue.offer(val+node.left.val);
                }
                if(node.right!=null){
                    nodeQueue.offer(node.right);
                    valQueue.offer(val+node.right.val);
                }
            }
        }
        return false;
    }
}