读前福利：几百本互联网技术书籍送给大家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
|
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)
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
玩的开心呀 ღ( ´･ᴗ･` )
最后
在这里给大家准备了几百本的互联网技术类书籍，需要的来下载吧！点击获取
有任何问题，欢迎随时交流!!!
