路径总和

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回true, 因为存在目标和为22的根节点到叶子节点的路径5->4->11->2。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        # sum减去根节点的val
        sum-=root.val
        # 如果没有左子树和右子树，说明到了根节点
        if not root.left and not root.right:
            return sum==0
        # 递归遍历左右子树
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)

113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

# 返回:
[
   [5,4,11,2],
   [5,8,4,5]
]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None



# 方法一、递归法
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        
        # 深度优先搜索该树
        def dfs(root,tmp,sum):
            # 确定递归的停止条件 
            if not root:
                return 
            # 如果到达根节点了，并且sum-root.val为0
            # 那么就可以将tmp数组添加root.val,并给res添加路径
            if not root.left and not root.right and sum-root.val==0:
                tmp.append(root.val)
                res.append(tmp)
            # 递归访问左右子树，更新此时的参数为 tmp+[root.val],sum-root.val
            dfs(root.left,tmp+[root.val],sum-root.val)
            dfs(root.right,tmp+[root.val],sum-root.val)
        res=[]
        dfs(root,[],sum)
        return res

# 方法二、迭代法
class Solution:
    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
        if not root: return []
        # 将root节点和值入栈
        stack = [([root.val], root)]
        res = []
        while stack:
            # 将节点和路径出栈 
            tmp, node = stack.pop()
            # 如果到达根节点并且路径和满足，就将路径添加到res
            if not node.right and not node.left and sum(tmp) == sum_:
                res.append(tmp)
            # 将左右子数入栈
            if node.right:
                stack.append((tmp + [node.right.val], node.right))
            if node.left:
                stack.append((tmp + [node.left.val], node.left))
        return res

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Jason
• 本文链接： https://caicaijason.github.io/2019/12/05/路径总和/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！