112. 路径总和（简单）

小灰灰 2022-09-10 05:20 181阅读 0赞

Leetcode链接：[112. 路径总和][112.]

### 题目描述 ###

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

示例 1：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_16_color_FFFFFF_t_70_g_se_x_16]

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

示例 2：

> 输入：root = \[1,2,3\], targetSum = 5  
> 输出：false  
> ![在这里插入图片描述][1eda2b6980c44d10acbd27332c4e48c9.png]

示例 3：

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

提示：

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

### 源码 ###

##### 深度优先搜索 #####

基本思想：

*  访问过当前节点`node`的值，使`targetSum = targetSum - node.val`
 *  判断是否是叶子节点`if(root.left == null && root.right == null)`
 *  是叶子节点后，判断`targetSum == root.val`

##### 广度优先搜索 #####

*  使用两个队列进行处理，一个队列是存放`TreeNode节点`，一个队列是存放`对应该节点路径的和`。

/**
     * 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;
            //存放TreeNode节点
            Queue<TreeNode> queue_node = new LinkedList<>();
            //存放根节点到node的路径和
            Queue<Integer> queue_val = new LinkedList<>();
    
            queue_node.offer(root);
            queue_val.offer(root.val);
    
            while(!queue_node.isEmpty()){
        
                TreeNode node = queue_node.poll();
                int node_val = queue_val.poll();
    
                if(node.left == null && node.right == null){
        
                    if(node_val == targetSum) return true;
                    //如果不相等，则寻找下一个节点；
                    else continue;
                }
    
                if(node.left != null){
        
                    queue_node.offer(node.left);
                    queue_val.offer(node.left.val + node_val);
                }
                if(node.right != null){
        
                    queue_node.offer(node.right);
                    queue_val.offer(node.right.val + node_val);
                }
            }
            return false;
        }
    }

[112.]: https://leetcode-cn.com/problems/path-sum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8f4d8f9c4b1c4b0b8b1cf037d9f15597.png
[1eda2b6980c44d10acbd27332c4e48c9.png]: /images/20220829/fe56a738326c4de1a1dbbeb70b7ff9eb.png