0%

leetcode112 | 路径总和

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw


每天分享一个LeetCode题目

每天 5 分钟,一起进步

LeetCode112 路径总和,地址: https://leetcode-cn.com/problems/path-sum/

这道题目是 LeetCode 中「树」路径总和的第一个题目,就是给定 targetSum ,去判断,自顶而下到叶子结点,整个路径有没有路径和为 targetSum 的路径,有就返回 True,否则,返回 False。

树结点定义

1
2
3
4
5
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

递归方式

依然递归方式比较简单,就是一个先续遍历,先判断当前结点是否有孩子结点

如果有,则继续向下判断

如果没有,则该结点是叶子结点,判断是否满足给定目标值 targetSum 的条件。

具体思路是,在不断的先序递归遍历中,每次递归,都要用 targetSum 减去当前结点值,当到了叶子结点的时候,判断被不断减掉的 targetSum 当前的值是否和单当前结点值相同。若相同,返回 True。

1
2
3
4
5
6
def hasPathSum(self, root, targetSum):
if not root:
return False
if not root.left and not root.right and targetSum == root.val:
return True
return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

这就是一个简单的先序遍历,对于递归思维方式解决有关「树」的题目的时候,还是比较不容易想清楚.

多思考,多练习。

非递归方式

使用层序遍历的思考过程。

在不断遍历访问结点的过程中,需要记录两个值,一个是结点,另外一个是从根结点到当前结点路径和,这里我们用 Python 的元祖来表示(结点, 从根结点到当前结点路径和)

层序遍历的过程,这里先不赘述了,需要看详细说明的,可以转战这里https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw,有详细的图表说明。

看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def hasPathSum_bfs(self, root, targetSum):
if not root:
return False
queue = collections.deque()
# 使用元祖存放结点信息(结点,当前结点自顶向下路径和)
queue.append((root, root.val))
while queue:
node, node_val = queue.pop()
if not node.left and not node.right and node_val == targetSum:
return True
if node.left:
queue.appendleft((node.left, node.left.val + node_val))
if node.right:
queue.appendleft((node.right, node.right.val + node_val))
return False

尤其是很多地方都会使用像这种 BFS 的方式进行遍历访问,而且主要适用于一些从顶向下的题目。这个是一道很典型的从顶向下题目。

对于这一类从顶向下的题目,使用 BFS 的思路是非常清晰的。

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# -*- coding:utf-8 -*-
# !/usr/bin/env python

import collections

# 树结点类
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right


class Solution(object):
def hasPathSum(self, root, targetSum):
if not root:
return False
if not root.left and not root.right and targetSum == root.val:
return True
return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

def hasPathSum_bfs(self, root, targetSum):
if not root:
return False
queue = collections.deque()
# 使用元祖存放结点信息(结点,当前结点自顶向下路径和)
queue.append((root, root.val))
while queue:
node, node_val = queue.pop()
if not node.left and not node.right and node_val == targetSum:
return True
if node.left:
queue.appendleft((node.left, node.left.val + node_val))
if node.right:
queue.appendleft((node.right, node.right.val + node_val))
return False


if __name__ == "__main__":
# 新建节点
root = TreeNode(5)
node_B = TreeNode(3)
node_C = TreeNode(6)
node_D = TreeNode(1)
node_E = TreeNode(2)
node_F = TreeNode(4)
node_G = TreeNode(9)
node_H = TreeNode(7)
node_I = TreeNode(0)
node_J = TreeNode(9)
# 构建二叉树
# 5
# / \
# 3 6
# / \ / \
# 1 2 4 9
# / \
# 7 0
# \
# 9
root.left, root.right = node_B, node_C
node_B.left, node_B.right = node_D, node_E
node_C.left, node_C.right = node_F, node_G
node_D.left, node_D.right = node_H, node_I
node_I.right = node_J

s = Solution()
print(s.hasPathSum(root, 18))
print(s.hasPathSum_bfs(root, 18))

Github

https://github.com/xiaozhutec/PyCode

玩的开心呀 ღ( ´・ᴗ・` )

最后

在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!

------ 全文结束------