8.＜tag-二叉树和回溯＞lt.112. 路径总和

X.＜tag-数组和二分查找＞-lt.xx-xxxxxx + lt.xx-xxxxxx

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {

        if(root == null)return false;
        return dfs(root, targetSum - root.val); /// !!!
    }
    //遍历二叉树的所有路径
    //遍历所有路径, 返回的是false
    public boolean dfs(TreeNode root, int count){
        
        //递归结束条件
        if(root.left == null && root.right == null && count == 0)return true;
        if(root.left == null && root.right == null  )return false;

        //单层递归逻辑
        //对左子树的处理:
        if(root.left != null){
            count -= root.left.val;
            if(dfs(root.left, count))return true;
            count += root.left.val;
        }

        //对右子树的处理
        if(root.right != null){
            count -= root.right.val;
            if(dfs(root.right, count))return true;
            count += root.right.val;
        }

        return false;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        Queue nodes = new LinkedList<>();
        Queue nodesVal = new LinkedList<>();

        if(root == null)return false;

        nodes.add(root);
        nodesVal.add(root.val);

        while(!nodes.isEmpty()){
            root = nodes.poll();
            int temp = nodesVal.poll();

            if(root.left == null && root.right == null){
                if(temp == targetSum)return true;
                continue;
            }

            if(root.left != null){
                nodes.add(root.left);
                nodesVal.add(root.left.val + temp);
            }

            if(root.right != null){
                nodes.add(root.right);
                nodesVal.add(root.right.val + temp);
            }
        }

        return false;
    }
}