[Leetcode][第112题][JAVA][路径总和][递归][队列]

谁借莪１个温暖的怀抱￠ 2023-02-23 12:01 16阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 递归 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(H)**  
![在这里插入图片描述][20200707103246862.png]  
**从根节点开始，每当遇到一个节点的时候，从目标值里扣除节点值，一直到叶子节点判断目标值是不是被扣完。**

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

**声明一个变量记录已经经过的节点的值之和，每经过一个节点就加上这个节点的值，在叶子节点判断变量值是否为目标值。**

public boolean hasPathSum(TreeNode root, int sum) { 
          return  helper(root,0,sum);
        }
        public boolean helper(TreeNode root,int cur,int sum)
        { 
          if(root==null)
              return false;
            cur=cur+root.val;
            if(root.left==null&&root.right==null)
            { 
                return cur==sum;
            }else
            { 
                return helper(root.left,cur,sum)|| helper(root.right,cur,sum);
            }
        }
    
    
    。

###### 2. 广度优先搜索 ######

![在这里插入图片描述][20200707103146510.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200707103224279.png]

class Solution { 
        public boolean hasPathSum(TreeNode root, int sum) { 
            if (root == null) { 
                return false;
            }
            Queue<TreeNode> queNode = new LinkedList<TreeNode>();
            Queue<Integer> queVal = new LinkedList<Integer>();
            queNode.offer(root);
            queVal.offer(root.val);
            while (!queNode.isEmpty()) { 
                TreeNode now = queNode.poll();
                int temp = queVal.poll();
                if (now.left == null && now.right == null) { 
                    if (temp == sum) { 
                        return true;
                    }
                    continue;
                }
                if (now.left != null) { 
                    queNode.offer(now.left);
                    queVal.offer(now.left.val + temp);
                }
                if (now.right != null) { 
                    queNode.offer(now.right);
                    queVal.offer(now.right.val + temp);
                }
            }
            return false;
        }
    }

#### 【总结】 ####

###### 1.注意事项 ######

![在这里插入图片描述][20200707103040926.png]

###### 2.数的递归 ######

树的递归题目是非常有套路可循的，因为树有两个分支，所以在递归里也有两个分支，一般是通过 递归 A（||，&&）递归 B 来实现分支的。只要明白了这一点，递归函数就不会很难设计。

###### 3.巧妙使用了两个队列 一个队列保存遍历节点 另一节点保存和 ######

参考链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/

参考链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-jie-da-by-commonheart/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707102956849.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200707103232612.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200707103246862.png]: https://img-blog.csdnimg.cn/20200707103246862.png
[20200707103146510.png]: https://img-blog.csdnimg.cn/20200707103146510.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200707103102573.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020070710315321.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200707103224279.png]: https://img-blog.csdnimg.cn/20200707103224279.png
[20200707103040926.png]: https://img-blog.csdnimg.cn/20200707103040926.png