LeetCode 112 [Path Sum]
程序员文章站
2024-01-05 11:41:10
...
原题
给出一个二叉树和一个sum, 判断是否存在一条自根节点到叶节点路径,使路径和等于sum
样例
给出下面的二叉树 和 sum = 22
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 True 因为5->4->11->2 的和等于22
解题思路
- 二叉树遍历
- 如果找到一个根到叶的路径求和,如果等于sum直接返回True
完整代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if self.helper(root, 0, sum) == True:
return True
return False
def helper(self, root, subSum, sum):
if root.left == None and root.right == None:
if subSum + root.val == sum:
return True
if root.left and self.helper(root.left, subSum + root.val, sum):
return True
if root.right and self.helper(root.right, subSum + root.val, sum):
return True
推荐阅读
-
LeetCode 112 [Path Sum]
-
LeetCode 112 Path Sum
-
leetcode【112】Path Sum
-
Leetcode算法刷题:第112题 Path Sum
-
leetcode(112):Path Sum
-
leetcode[112]Path Sum
-
LeetCode 112 Path Sum
-
Leetcode Two Sum (java)Longest Substring Without Repeating Characters
-
[LeetCode 4.18] Minimum Path Sum
-
POJ3126 Prime Path(BFS) 类似于Leetcode 单词接龙