路径总和

Leetcode Link: 112. 路径总和 - 力扣（LeetCode） (leetcode-cn.com)

题目

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

本题关键点，非常容易错!!!!不是不会，是不审题!!!

1. 只是判断有没有
2. 路径必须根节点到叶子节点

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

解法一

思路：自己的思路，不对。 本题的特殊之处在如果存在从根节点到叶节点的路径才返回 True，而不存在这种路径则返回False

那么会存在如下几个特殊情况

1. 输入二叉树[1, 2]，targetSum=1, 此时根节点满足 targetSum，但是它不是叶子节点，所以返回 False
2. 输入二叉树只有根节点，此时根节点值等于targetSum，它既是根节点也是叶子节点，应该返回 True
3. 输入二叉树为空，返回False

特殊情况1和2很关键，本题的需要特别注意是的判断是不是叶子节点，如果不判断是不是叶子节点，一定会出错！

题解：提交了多次都不对，下面的依然不对，不知道哪里有问题，改正了。

class Solution:
    def hasPathSum(self, root, targetSum):
        # 特殊情况1，输入为空
        if not root:
            return False
        # 特殊情况2，只有一个节点
        if not root.left and not root.right:
            return root.val == targetSum
        
        def recur(cur, tar):
            if not cur:
                return False
            # 判断是不是叶子节点
            if not cur.Left and not cur. Right:
	            # 他妈的，这里错了，一直写的是 tar==0，叶子节点要是满足路径，那么就需要等于tar，而不是0，操了。
                return tar == cur.val
            
            tar = tar - cur.val
            left = recur(cur.left, tar)
            right = recur(cur.right, tar)
 
            return left or right
        return recur(root, targetSum)
 

解法二

思路： 思路同上，网友答案。 各种情况融合到了一起

题解：

 
class Solution(object):
    def hasPathSum(self, root, sum):
        if not root: 
            return False
        # 判断是不是叶子节点
        if not root.left and not root.right:
            return sum == root.val
        # 更新目标值
        sum =  sum - root.val
        left = self.hasPathSum(root.left,sum) 
        right = self.hasPathSum(root.right,sum) 
        return left or right

解法三

思路：BFS，队列

（自己）开辟两个队列，一个保存当前节点，一个保存节点对应的目标值，注意判断叶子节点

题解：

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        '''BFS'''
        if not root:
            return False
        q = collections.deque()
        q.append(root)
        # target队列，存储至当前节点的目标值
        # 简单想，只含有1个节点，若 target == root.val时候，则返回True
        # 因此q_tar存储的应该是“上一个”节点-target的值
        q_tar = collections.deque()
        q_tar.append(targetSum) 
 
        res = False
        while(q):
            cur_target = q_tar.popleft()
            cur = q.popleft()
            if not cur.left and not cur.right:
                res = res or (cur_target == cur.val)
            if cur.right: 
                q.append(cur.right)
                q_tar.append(cur_target-cur.val)
            if cur.left: 
                q.append(cur.left)
                q_tar.append(cur_target-cur.val)
        return res

解法四

思路：栈

题解：暂略

启发和联系