Leetcode112. 路径总和

题目描述

 /**
     * 
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
     *
     * 叶子节点 是指没有子节点的节点。
     *
     */

思路分析

1. 判断二叉树的叶子节点所在路径的节点值总和是否等于目标值,可以使用两个队列，一个队列记录所有的节点，一个队列记录节点值，两队列中的元素一一对应
2. 当且仅当当前节点为叶子节点，即当前节点的左右子树为空，并且当前节点路径上值总和等于目标值，才返回空
3. 如果不是叶子节点，继续记录其子节点和子节点路径上的节点值总和，继续判断
4. 如果遍历完所有的节点，没有满足条件，则返回false
5. 详解见下

源码及分析

 /**
     *
     * @param root 根节点
     * @param targetSum 目标值
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //判断跟节点是否为空
        if (root == null){
            return false;
        }
        //定义两个队列，一个用于存储当前遍历的节点，一个用于存储当前路径的节点值总和
        Queue<TreeNode> nodes = new LinkedList<>();
        Queue<Integer> val = new LinkedList<>();
        //根节点及其值入队列
        nodes.offer(root);
        val.offer(root.val);
        //循环取二叉树的所有节点
        while (!nodes.isEmpty()){
            //两个队列中节点和其节点值是对应的
            TreeNode node = nodes.poll();
            Integer temp = val.poll();
            //如果当前节点是叶子节点，判断其路径上的节点值是否等于目标值
            if (node.left == null && node.right == null){
                if (temp == targetSum){
                    return true;
                }
                continue;
            }
            //再判断当前节点是否有子节点，如何有子节点，将其入队列
            if (node.left != null){
                nodes.offer(node.left);
                val.offer(temp + node.left.val);
            }
            if (node.right != null){
                nodes.offer(node.right);
                val.offer(temp + node.right.val);
            }
        }
        return false;

    }