Leetcode刷题100天—112. 路径总和( 二叉树)—day33

r囧r小猫 2022-09-13 00:21 151阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210909210721807][]

#### [112. 路径总和][112.] ####

难度简单660收藏分享切换为英文接收动态反馈

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

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

**示例 1：**

![img][]

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    输出：true

**示例 2：**

![img][img 1]

输入：root = [1,2,3], targetSum = 5
    输出：false

**示例 3：**

输入：root = [1,2], targetSum = 0
    输出：false

**提示：**

*  树中节点的数目在范围 `[0, 5000]` 内
 *  `-1000 <= Node.val <= 1000`
 *  `-1000 <= targetSum <= 1000`

package 二叉树;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class _112_路径总和 { 
    // 可以采用广度优先搜索
        public boolean hasPathSum(TreeNode root, int targetSum) { 
        	if (root==null) { 
    			return false;
    		}
    // 定义存入节点的队列
            Queue<TreeNode> queNode = new LinkedList<TreeNode>();
    // 入队顶元素
            queNode.offer(root);
            while (!queNode.isEmpty()) { 
    // 出队
                TreeNode now = queNode.poll();
    // 如果遍历到了底部
                if (now.left == null && now.right == null) { 
                    if (now.val == targetSum) { 
                        return true;
                    }
                    continue;
                }
    // 遍历左节点
                if (now.left != null) { 
                	now.left.val+=now.val;
                    queNode.offer(now.left);
                }
    // 遍历右节点
                if (now.right != null) { 
                	now.right.val += now.val;
                    queNode.offer(now.right);
                }
            }
            return false;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210909210721807]: /images/20220828/105aa4ceb254408b838bce806f777ab4.png
[112.]: https://leetcode-cn.com/problems/path-sum/
[img]: /images/20220828/fa0eb788723640348b751e8d00db2e25.png
[img 1]: /images/20220828/df48016ff5d64d2bb75a3c379366acae.png