|
112. 路径总和
难度简单518收藏分享切换为英文接收动态反馈
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
提示：
- 树中节点的数目在范围
[0, 5000] 内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
开始理解题目以为路径开头只能是根节，即整个路径只能是左子树或只能是右子数，看了官网题解，原来可以同时包含左右子树，只要和等于目标和即可。
1、广度优先遍历，只有遇到叶子节点且路径和等于目标和才返回成功。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def hasPathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: bool
"""
if root is None:
return False
que = []
que.append((root, root.val))
while que:
cur_node, cur_path_sum = que.pop(0)
if not cur_node.left and not cur_node.right and cur_path_sum == targetSum:
return True
if cur_node.left:
que.append((cur_node.left, cur_path_sum + cur_node.left.val))
if cur_node.right:
que.append((cur_node.right, cur_path_sum + cur_node.right.val))
return False
2、深度优先遍历中的前序遍历，递归方式：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def hasPathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: bool
"""
if root is None:
return False
if not root.left and not root.right:
return targetSum == root.val
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
| 
转播
