admin 管理员组

文章数量: 1087678

[勇者闯LeetCode] 112. Path Sum

[勇者闯LeetCode] 112. Path Sum

Description

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22, return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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

Information

  • Tags: Tree | Depth-first Search
  • Difficulty: Easy

Solution

使用深度优先搜索，遇到叶节点时判断路径的和是否与目标值相等。

Python Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""if root is None:return Falseif root.left is None and root.right is None and root.val == sum:return Trueelse:return self.hasPathSum(root.left, sum-root.val) or\self.hasPathSum(root.right, sum-root.val)

本文标签： 勇者闯LeetCode 112 Path Sum

版权声明：本文标题：[勇者闯LeetCode] 112. Path Sum 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1694393384a251540.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。