[112][简单][BFS][DFS] 路径总和

题目描述

112. 路径总和

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

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

示例:

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

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

解题思路

BFS

比较直接的思路是广度优先搜索. 结合队列, 从根节点开始, 搜索这个结点连接的所有子节点, 将子节点, 以及到此子节点为止路径之和压入到队列当中. 然后从队列中按照先入先出的原则依次取出节点, 同上所有子节点并压入队列, 不断循环, 直到遇到叶子结点且此时路径和为指定的sum值, 返回True, 否则直到队列为空终止, 并返回False.

# 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

        queue = collections.deque([(root, root.val)])
        while queue:
            cur_node, cur_val = queue.popleft()
            if cur_node.left is None and cur_node.right is None:
                if cur_val == sum:
                    return True

            if cur_node.left:
                queue.append((cur_node.left, cur_val + cur_node.left.val))
            if cur_node.right:
                queue.append((cur_node.right, cur_val + cur_node.right.val))
        return False

DFS

使用DFS思路绕一些, 需要通过递归实现. 首先, 我们得沿着一条路走到黑, 父节点将问题交给子节点时, 问题就转换成了以该子节点为根节点的二叉树, 是否存在从根节点到叶子结点的路径和为sum-parnet.value. 其中对于整个树的根节点来说就是指定的目标和, parnet.value对于整个树的根节点来说是根节点的值. 按照这个思路递归下去, 遇到下面两种情况返回:

• root为None, 说明其父节点为叶子结点, 这条路径无法满足, 返回False

• root为叶子节点且值正好等于剩余的sum值, 返回True

代码如下:

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None and root.val == sum:
            return True

        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)