leetcode(112):Path Sum
程序员文章站
2024-01-05 11:19:40
...
题目: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
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
题目分析:判断是否从根结点到叶子节点有和为固定值的分支,需要不断的统计此刻的和,然后对其来进行判断。
python代码实现:
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root == None:
return False
if root.left == None and root.right == None:
if root.val == sum:
return True
return False
if root.left != None:
root.left.val += root.val
if self.hasPathSum(root.left, sum) == True:
return True
if root.right != None:
root.right.val += root.val
if self.hasPathSum(root.right, sum) == True:
return True
return False
以上的代码,虽然实现了功能,但不好之处在于改变了每个节点的值,也就是改变了原始的结构,这对于数据来说是毁灭性的求解,所以,肯定是不好的,然后对之进行改进。
# 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 root == None:
return False
if root.left == None and root.right == None:
if root.val == sum:
return True
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
这样子改进,然后就会好很多了,这样子可以不改变原有的结构,然后还判断出了是否存在这样的一条从根节点到叶子节点的路径和为固定值的判断。
大佬的代码:
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a boolean
# 1:27
def hasPathSum(self, root, sum):
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
sum -= root.val
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
大佬的递归的思想跟我的思想重合的,只是大佬对于判断条件的写法更加简略,更加简洁,学习就好。
DFS Recursively
def hasPathSum1(self, root, sum):
res = []
self.dfs(root, sum, res)
return any(res)
def dfs(self, root, target, res):
if root:
if not root.left and not root.right:
if root.val == target:
res.append(True)
if root.left:
self.dfs(root.left, target-root.val, res)
if root.right:
self.dfs(root.right, target-root.val, res)
这个题目中,我们又学到了any(),内嵌函数的用法。
DFS with stack
def hasPathSum2(self, root, sum):
if not root:
return False
stack = [(root, root.val)]
while stack:
curr, val = stack.pop()
if not curr.left and not curr.right:
if val == sum:
return True
if curr.right:
stack.append((curr.right, val+curr.right.val))
if curr.left:
stack.append((curr.left, val+curr.left.val))
return False
BFS with queue
def hasPathSum(self, root, sum):
if not root:
return False
queue = [(root, sum-root.val)]
while queue:
curr, val = queue.pop(0)
if not curr.left and not curr.right:
if val == 0:
return True
if curr.left:
queue.append((curr.left, val-curr.left.val))
if curr.right:
queue.append((curr.right, val-curr.right.val))
return False
推荐阅读
-
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 单词接龙
-
LeetCode 15: 3Sum题解(python)
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
LeetCode - 1. Two Sum(8ms)
-
LeetCode_#1_两数之和 Two Sum_C++题解