112. 路径总和

Difficulty
easy
Tags
二叉树
URL
https://leetcode-cn.com/problems/path-sum/
Star
❤
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
notion imagenotion image
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
notion imagenotion image
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
提示：
  • 树中节点的数目在范围 [0, 5000] 内
  • 1000 <= Node.val <= 1000
  • 1000 <= targetSum <= 1000
通过次数212,145提交次数406,198

法1 回溯法

思路
典型的采用回溯算法的题目。
注意递归的返回值，总结如下：
  • 如果需要遍历整棵二叉树，则递归过程中一般不需要返回值
  • 如果需要在二叉树中遍历查找某个满足的条件，则需要返回值，且是及时的返回,这样就不会再遍历后面的子树了
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        return self.backtrack(node=root, path=[root.val], target=targetSum)
    
    def backtrack(self, node, path, target):
        # 如果是叶子节点
        if node.left is None and node.right is None:
            if sum(path) == target:
                return True
            else:
                return False
        # 不是叶子节点就需要递归
        left_bool, right_bool = False, False

        if node.left:
            path.append(node.left.val)  # 做选择
            left_bool = self.backtrack(node.left, path, target)
            if left_bool: # 及时返回
                return True
            path.pop()   # 撤销选择
        if node.right:
            path.append(node.right.val) # 做选择
            right_bool = self.backtrack(node.right, path, target)
            if right_bool: # 及时返回
                return True
            path.pop()   # 撤销选择
        return False
优化：一般查找某某之和等于target的，都可以通过减法来做，就是令target减掉遍历过的每个值，然后判断是否为0
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        return self.backtrack(node=root, target=targetSum-root.val)
    
    def backtrack(self, node, target):
        # 如果是叶子节点
        if node.left is None and node.right is None:
            if target == 0:
                return True
            else:
                return False
        # 不是叶子节点就需要递归
        left_bool, right_bool = False, False

        if node.left:
            target -= node.left.val  # 做选择
            left_bool = self.backtrack(node.left, target)
            if left_bool: # 及时返回
                return True
            target += node.left.val   # 撤销选择
        if node.right:
            target -= node.right.val  # 做选择
            right_bool = self.backtrack(node.right, target)
            if right_bool: # 及时返回
                return True
            target += node.right.val    # 撤销选择
        return False
精简代码：进行隐式的回溯
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        return self.backtrack(node=root, target=targetSum-root.val)
    
    def backtrack(self, node, target):
        # 如果是叶子节点
        if node.left is None and node.right is None:
            if target == 0:
                return True
            else:
                return False

        # 不是叶子节点就需要递归
        if node.left:
            if self.backtrack(node.left, target-node.left.val):
                return True
        if node.right:
            if self.backtrack(node.right, target-node.right.val):
                return True
        return False
精简代码：前面是判断target == 0, 其实可以在访问叶子节点node时就判断 target == node.val,这样就会少去递归一层。具体做法就是，在递归遍历左子树的时候，target - 当前节点的val,而不是-左子节点的val
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        return self.backtrack(node=root, target=targetSum)
    
    def backtrack(self, node, target):
        if node is None:
            return False
        # 如果是叶子节点
        if node.left is None and node.right is None and target == node.val:
            return True

        # 不是叶子节点就需要递归
        if self.backtrack(node.left, target-node.val):
            return True
        if self.backtrack(node.right, target-node.val):
            return True
        return False

法2 迭代

思路
同
🛵
257. 二叉树的所有路径 类似，在遍历每一个节点时，把从跟节点到当前节点的值都放到一个列表中，再将该列表放到队列/栈中
这样就可以采用先序/层次 等方法来遍历二叉树，在访问节点时，判断从根节点到该节点的路径值之和是否为target
题解
层次遍历
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        queue = []
        queue.append(root)
        queue.append([root.val])
        while len(queue) > 0:
            node = queue.pop(0)
            path_sum = queue.pop(0)
            if node.left is None and node.right is None:
                if sum(path_sum) == targetSum:
                    return True
            if node.left:
                queue.append(node.left)
                queue.append(path_sum+[node.left.val])
            if node.right:
                queue.append(node.right)
                queue.append(path_sum+[node.right.val])
        return False
先序遍历
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        stack = []
        stack.append(root)
        stack.append([root.val])
        while len(stack) > 0:
            path_sum = stack.pop()
            node = stack.pop()
            if node.left is None and node.right is None:
                if sum(path_sum) == targetSum:
                    return True
            if node.left:
                stack.append(node.left)
                stack.append(path_sum+[node.left.val])
            if node.right:
                stack.append(node.right)
                stack.append(path_sum+[node.right.val])
        return False
优化：现在记录了从根节点到当前访问节点的路径值，但其实可以只记录target - 当前节点值，然后最后到叶子节点的时候判断 是否为0
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        stack = []
        stack.append(root)
        stack.append(targetSum-root.val)
        while len(stack) > 0:
            value = stack.pop()
            node = stack.pop()
            if node.left is None and node.right is None:
                if value  == 0:
                    return True
            if node.left:
                stack.append(node.left)
                stack.append(value-node.left.val)
            if node.right:
                stack.append(node.right)
                stack.append(value-node.right.val)
        return False