零
刷题复盘进度
大家好,我是Johngo!
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:95637932-4779-4317-a904-2dc0f98b2324
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5d37cf2f-7613-4b04-a6d5-b2de9d8b9cd8
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:696d7e49-5d69-40f5-a298-8aef573304a7
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:67ace851-b321-4b66-808a-14994bd3cb54
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3ff018ed-f224-4b32-af5b-11946226edcf
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ac90473b-e2dd-4d70-bef4-d135b5ac0016
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:19ad85ab-69c4-42b4-b002-1d88fd14199e
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:75157011-1bce-48c7-bc00-27831eccb726
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3f298b7d-40a9-4bd7-9390-5eaf7725a936
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:61d9494a-9330-46b2-b7a8-1003f95d0901
涉及到的题目
104.二叉树的最大深度: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
112.路径总和: https://leetcode-cn.com/problems/path-sum
113.路径总和 II: https://leetcode-cn.com/problems/path-sum-ii
437.路径总和 III: https://leetcode-cn.com/problems/path-sum-iii
257.二叉树的所有路径: https://leetcode-cn.com/problems/binary-tree-paths
129.求根节点到叶节点数字之和: https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
988.从叶结点开始的最小字符串: https://leetcode-cn.com/problems/smallest-string-starting-from-leaf
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:12053f09-de9b-4a28-a720-2df1fe0c78f4
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:051d8435-20fb-4377-b9dc-80b4b651ba6f
第一类:BFS,广度优先搜索,利用层次遍历的方式进行解决
第二类:DFS,深度优先搜索,利用前中后序遍历树的方式进行问题的解决
既然先说的 BFS,咱们就从 BFS 先说起,后面再描述 DFS 的解决方式。
一
BFS 思路
BFS(Breadth First Search):广度优先搜索
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a14614a9-0231-43a6-9ed3-bd40000a0ec8
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:463c290f-6d69-451e-8d4b-2b48e7b28107
很简单的一个过程。循环判断队列 queue 中是否有元素,如果有,访问该元素并且判断该结点元素是否有孩子结点,如果有,孩子结点依次入队 queue,否则,继续循环执行。
再来看看代码:
res = []
while queue:
node = queue.pop()
res.append(node.val)
if node.left:
queue.appendleft(node.left)
if node.right:
queue.appendleft(node.right)
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:0033a4f3-cf79-4f27-ad7c-0681d4491e1b
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:84cef888-7221-4aa2-90dd-985e219de42e
现在想要抛出 2 个引例,往上述代码中添加点作料,看是否可以很容易就解答。
引例一
遍历过程中能否记录根结点到当前结点的一些信息?
包括:
1、根结点到当前结点的路径信息
2、根结点到当前结点的路径和
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:62d38449-537a-4670-ae3d-52baf2d51d60
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:70547206-c8e6-46f1-8ab4-4a8f59294d05
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9f9c3227-6d98-4e43-9b1f-6c5dbd6af98e
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:42bdede1-4c3e-4844-9970-d356734e13e3
node 表示结点对象
node_path 表示根结点到当前结点路径
node_val 表示根结点到当前结点路径和
Python 中使用元祖进行表示结点的三元组信息:(node, node_path, node_val)
代码实现:
res = []
while queue:
node, node_path, node_val = queue.pop()
res.append((node, node_path, node_val))
if node.left:
queue.appendleft((node.left, node_path+str(node.left), node_val+node.left.val))
if node.right:
queue.appendleft((node.right, node_path+str(node.right), node_val+node.right.val))
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:85ee3b61-e8c3-4e91-9483-9159a9828c9f
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b44e8a46-76cd-4191-a822-c34ae06cd808
引例二
能否在层序遍历过程中,携带一个值进行层序的记录?
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:aea2da24-3519-4be8-ad82-5ad9717ba6dd
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2b273ec3-edce-4bfd-860c-f75bb159d5fc
这个的思路,其实很容易就让我想到之前二叉树按照 LeetCode 形式打印的一个过程(不太记得的小伙伴可以查看 https://mp.weixin.qq.com/s/MkCF5TaR1JD3F3E2MKlgVw 回忆下关于LeetCode的层序遍历)
下面我又把 LeetCode 中要求层次遍历的图解过程放出来,作为回忆参考!
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e05d9a4d-83fc-44a2-ad43-0dbd996ed173
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1a1b769d-1a86-45ab-bff0-53a4691fa543
即,在每一层遍历的时候,进行 node_depth+=1
的操作。先来看最初代码的样子(还。。记得吗~?):
def levelOrder(self, root):
res = []
if not root:
return res
queue = [root]
while queue:
level_queue = [] # 临时记录每一层结点
level_res = [] # 临时记录每一行的结点值
for node in queue:
level_res.append(node.val)
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
res.append(level_res)
return res
每一层的遍历,都是 queue 被赋予新的一个队列 level_queue,即新的一层的所有结点集。
在此思路的基础上
首先,初始化变量用作记录层序值
node_depth = 0
其次,在每一次while queue:
之后进行node_depth+=1
最后node_depth
的值就是你想要的某一层的值
看代码小改动后的实现
def levelOrder(self, root):
res = []
# 层序记录
node_depth = 0
if not root:
return res
queue = [root]
while queue:
node_depth += 1 # 层序值+1
level_queue = []
level_res = []
for node in queue:
level_res.append(node.val)
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
res.append(level_res)
return res
哈哈对,不要找了!就是 有注释的那两行,只不过要取的 node_depth
的值是你所需要的那个值。
比如说,最大深度的计算,那就是最后 node_depth
的值;如果是根结点到某一结点路径和你给到的 target
值一致的时候的那个深度,那就是被满足结点所在层序的 node_depth
。
好!
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2388d476-30fb-4b17-b02e-ac6d74733eb1
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c9a1796d-4ebb-4703-8fb3-3d527b505cc8
利用上述「引例一」和「引例二」的思路举例看看对 LeetCode 中部分题目有什么帮助?
LeetCode104.二叉树的最大深度
题目链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/104.二叉树的最大深度.py
其实就是「引例二」中携带一个值进行层序的记录,最后返回的 node_depth
就是二叉树的最大深度!
def maxDepth_bfs(self, root):
if not root:
return 0
queue = collections.deque()
# 初始化深度为 0
node_depth = 0
# 初始化队列中的结点元素 root
queue.appendleft(root)
while queue:
# 每一层的遍历,深度 +1
node_depth += 1
# 记录每一层的结点集合
level_queue = []
for node in queue:
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
return node_depth
是不是很容易就解决了!
再来看一个:
LeetCode112.路径总和:
题目链接:https://leetcode-cn.com/problems/path-sum
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/112.路径总和.py
LeetCode112题目是从根结点到叶子结点,是否存在路径和为 target
的一个路径。
如下图,如果咱们要找路径和为 target=16
的一个路径,利用「引例一」中的思路,很容易就可以判断,在最后一个结点中的三元组 (9, 1->2->4->9, 16)
中能够得到路径为 1->2->4->9
。
代码实现起来也很容易
def hasPathSum_bfs(self, root, targetSum):
if not root:
return False
queue = [(root, root.val)]
while queue:
node, node_sum = queue.pop(0)
if not node.left and not node.right and node_sum == targetSum:
return True
if node.left:
queue.append((node.left, node_sum+node.left.val))
if node.right:
queue.append((node.right, node_sum+node.right.val))
return False
这里返回了存在该路径,为 True
,如果想要返回路径,那么直接将路径返回就可以了!
再来看一个:
LeetCode257.二叉树的所有路径:
题目链接:https://leetcode-cn.com/problems/binary-tree-paths
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/257.二叉树的所有路径.py
就是要把所有从根结点开始到叶子结点所有的路径遍历出来。其实还是「引例一」中的思路,当遍历到叶子结点的时候,将所有叶子结点中的三元组中的路径值取出。例如叶子结点 (9, 1->2->4->9, 16)
中的路径为 1->2->4->9
取出。
可以得到一个路径集合:
[[1->3->6], [1->3->7], [1->2->4->8], [1->2->4->9]]
代码很类似
def binaryTreePaths_bfs(self, root):
res = []
if not root:
return res
queue = collections.deque()
queue.appendleft((root, str(root.val)+"->"))
while queue:
node, node_val = queue.pop()
if not node.left and not node.right:
res.append(node_val[0:-2])
if node.left:
queue.appendleft((node.left, node_val + str(node.left.val) + "->"))
if node.right:
queue.appendleft((node.right, node_val + str(node.right.val) + "->"))
return res
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1511e3f5-a405-46e2-837e-4af9388a0204
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a8234892-f6bc-4604-9aae-bed0bc3b2244
再来看最后一个例子:
LeetCode129.求根节点到叶节点数字之和
题目链接:https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/129.求根节点到叶节点数字之和.py
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d5d9f515-d3a6-4e6b-93df-bd1f45f380ca
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2d90a03f-e5ef-441f-86ea-73230b0a93cc
举例说,图中路径分别为 [[1->3->6], [1->3->7], [1->2->4->8], [1->2->4->9]]
,对应的数字为 [10, 11, 15, 16],那么,数字之和为 10+11+15+16=52
。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:8ef71e0a-6f92-4176-b978-87699716bce3
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a318cc54-3645-43fa-be3c-fad57cbf2e29
def sumNumbers_bfs(self, root):
res = []
sum = 0
if not root:
return 0
queue = collections.deque()
queue.append((root, str(root.val)))
while queue:
node, node_val = queue.pop()
if node and not node.left and not node.right:
res.append(node_val)
if node.left:
queue.appendleft((node.left, node_val+str(node.left.val)))
if node.right:
queue.appendleft((node.right, node_val+str(node.right.val)))
for item in res:
sum += int(item)
return sum
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b9e57225-edbc-4edb-93e6-7222b831c7a2
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:dd71142d-c646-4fad-8b04-3a5627617fdb
还有一些其他类似的题目,这里就先不说了,文章最开头给出的「自顶向下」这类题目都在 github:https://github.com/xiaozhutec/share_leetcode/tree/master/树 上进行了记录,细节代码可以参考。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c61dbdfd-feeb-41c5-8789-8c0debad350f
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b1149b72-ca19-4cb2-8f79-ae497ce38971
下面再总结下利用 DFS 的思路进行问题的解决。
二
DFS 思路
DFS(Depth First Search):深度优先搜索
回忆下之前的二叉树的递归遍历,也可以说是 DFS 的思路。之前在这篇文章中详细阐述过 https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ec65b2d7-582d-4b2e-9500-c24b7117071c
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:921219ef-6df5-4265-8027-2e51ee5fa9ef
很多时候我会利用一个很 easy 的思路是,将二叉树的递归遍历利用在「二叉树」的叶子结点以及再向上一层进行理解和问题的解决。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:310d6901-52cb-4847-ba1b-b9e3c20761c3
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:63dd353e-b7a1-40ab-b82f-aa64959d7b7f
二叉树的先序遍历:
def pre_order_traverse(self, head):
if head is None:
return
print(head.value, end=" ")
self.pre_order_traverse(head.left)
self.pre_order_traverse(head.right)
二叉树的中序遍历:
def in_order_traverse(self, head):
if head is None:
return
self.in_order_traverse(head.left)
print(head.value, end=" ")
self.in_order_traverse(head.right)
二叉树的后续遍历:
def post_order_traverse(self, head):
if head is None:
return
self.post_order_traverse(head.left)
self.post_order_traverse(head.right)
print(head.value, end=" ")
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f5b269b8-e476-4d7b-80b6-5d3a2cf4929d
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:87853f2e-b235-43e1-9e4f-eb548a922687
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:0508da90-e7df-4875-b7a5-6f6b9742928c
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:90403896-b020-4b81-b4e5-68f0240ab39b
这一期先把「自顶向下」这类题目运用 DFS 的思路说明白了!
利用二叉树的递归思路,其实很容易就可以解决这类问题,把 BFS 说到的题目用 DFS 思路解决一下,代码看起来更加的简洁,美观!
LeetCode104.二叉树的最大深度
题目链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/104.二叉树的最大深度.py
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d920c282-05cb-4c66-8f26-6bc5da794220
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2f53444d-28d8-4e3a-9011-91cd4de43ec0
def maxDepth_dfs(self, root):
if not root:
return 0
else:
max_left = self.maxDepth_dfs(root.left)
max_right = self.maxDepth_dfs(root.right)
return max(max_left, max_right) + 1
太简单了叭!!~~
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:afb8ab98-802c-439d-b0a4-3ce00a3f3eb9
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a148f1b0-bedf-49d7-a866-8343e1fb209a
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e0acdda4-2c9f-4709-892c-3369bac1d032
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:332291bb-f2a4-445f-95f5-ac3b9d5d8e09
a.当递归到叶子的时候,程序 return 0
,也就是递归使用 self.maxDepth_dfs(root.left)
以及 self.maxDepth_dfs(root.right)
的时候,返回值为 0;
b.往上考虑一层,递归使用 self.maxDepth_dfs(root.left)
或者 self.maxDepth_dfs(root.right)
的时候,返回值是 return max(max_left, max_right) + 1
, 是 【a.】的返回值 0+1
。
通过以上【a. b.】两点锁构造的思路进行代码的设计,一定是正确的。
重点重点重点:以上的【b.】,不是太容易理解,用心思考,恍然大悟的时候,真的很巧妙!
下一个题目:
LeetCode112.路径总和:
题目链接:https://leetcode-cn.com/problems/path-sum
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/112.路径总和.py
LeetCode112题目是从根结点,寻找路径和为 target
的一个路径。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:fda22918-2867-4681-82ee-ae63bce1be5d
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f72aaa12-c36c-4385-9d09-fe689419cc8c
def hasPathSum(self, root, targetSum):
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
思路点:递归将 targetSum-递归到的结点值
,直到遇到叶子结点的时候,刚好被完全减去,得到0。即存在该路径。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5eab70b6-38f7-4a9e-94a8-f5f0e94ce0ee
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:4a76785d-07fa-4d70-9bf0-8f09d2d0f4ef
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:907dd30e-e5f4-438b-a091-e05b7dd3ddb5
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2f07e028-d17a-4ace-af65-d87a2833aa72
a.当递归到叶子的时候,程序判断叶子结点的值和 tagetSum
被减的剩余的值是否相等;
b.往上考虑一层,递归使用 self.hasPathSum(root.left, targetSum - root.val)
以及 self.hasPathSum(root.right, targetSum - root.val)
的时候,返回值是【a.】返回的值。
再来看一个:
LeetCode257.二叉树的所有路径:
题目链接:https://leetcode-cn.com/problems/binary-tree-paths
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/257.二叉树的所有路径.py
这个题目用 DFS 解决起来,同样是非常简洁的,但是中间多了一个步骤的记录,所以会多几行代码:
def binaryTreePaths_dfs(self, root):
res = []
if not root:
return res
def dfs(root, path):
if not root:
return
if root and not root.left and not root.right:
res.append(path + str(root.val))
if root.left:
dfs(root.left, path + str(root.val) + "->")
if root.right:
dfs(root.right, path + str(root.val) + "->")
dfs(root, "")
return res
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2a365f30-8d1b-4cea-8e43-65cdb659547f
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:dc2ded69-a885-4064-9877-288a7bbe3796
a.当递归到叶子的时候,没有左右孩子,直接将该结点加入到路径中来;
b.往上考虑一层,递归使用 dfs(root.left, path + str(root.val) + "->")
以及 dfs(root.right, path + str(root.val) + "->")
的时候,就是将当前结点值加入到路径中。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a71ae2b0-96a1-4af2-a4f4-cb70177f0733
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:4e9b44c5-58e5-4f07-ba77-61e0395040bb
再来看最后一个例子:
LeetCode129.求根节点到叶节点数字之和
题目链接:https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
GitHub解答:https://github.com/xiaozhutec/share_leetcode/blob/master/树/129.求根节点到叶节点数字之和.py
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9e7c3ea6-2226-467c-a7c6-e006a25724d0
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ca16b946-d491-4143-974c-4eeb42aa39f3
def sumNumbers_dfs(self, root):
res = [] # 所有路径集合
sum = 0 # 所有路径求和
def dfs(root, path):
if not root:
return
if root and not root.left and not root.right:
res.append(path + str(root.val))
if root.left:
dfs(root.left, path + str(root.val))
if root.right:
dfs(root.right, path + str(root.val))
dfs(root, "")
for item in res:
sum += int(item)
return sum
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:51ebe2e3-81f9-486c-83e2-35ea4171e7bc
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1bbd41aa-6e8e-48b3-a219-14a867acfc43
嗯。。大概本篇的「树-自顶向下」已经接近尾声,寻找刷题组织的小伙伴们可以一起参与进来,私信我就OK!咱们一起坚持!
三
总结唠叨几句
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6117c420-73d5-4c4e-9004-36bda298e7d4
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:168e2b09-7fd7-484c-abbf-7822dd319b03
关于「树-自顶向下」这类题目,既适合用 BFS 思路解决,又适合使用 DFS 的思路进行解决。
用 BFS 解决问题的时候,思路清晰,代码稍微看起来会有些多!
可是用 DFS 的情况是,代码简洁,但是思路有时候会有些混乱,需要大量的练习才能逐渐的清晰起来!
下一期是讲透树 | 非自顶向下题目专题》,专门说说「树-非自顶向下」这一类,不知道会不会再有最后复盘的一期,看思路而定吧。
代码和本文的文档都在 https://github.com/xiaozhutec/share_leetcode,需要的小伙伴可以自行下载代码运行跑起来!方便的话给个 star。谢过大家!
Original: https://www.cnblogs.com/yydsxiaozhu/p/15531488.html
Author: 技术gogogo
Title: 【完虐算法】自顶向下专题类目 全复盘
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/563867/
转载文章受原作者版权保护。转载请注明原作者出处!