Algorithm
本周选择的算法题是：Merge Two Binary Trees。
规则
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Constraints:
- The number of nodes in both trees is in the range
[0, 2000]. -104 <= Node.val <= 104
Solution
递归版：
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1: return root2
if not root2: return root1
root = TreeNode(root1.val + root2.val)
root.left = self.mergeTrees(root1.left, root2.left)
root.right = self.mergeTrees(root1.right, root2.right)
return root
迭代版：
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1: return root2
stack = [(root1, root2)]
while stack:
r1, r2 = stack.pop(0)
if not r2: continue
r1.val += r2.val
if not r1.left:
r1.left = r2.left
else:
stack.append((r1.left, r2.left))
if not r1.right:
r1.right = r2.right
else:
stack.append((r1.right, r2.right))
return root1
Review
Python Concurrency: The tricky Bits
这篇文章详细描述了在 Python 里实现并发的几种方法，以及它们的性能表现，其中有一个观点很有价值，即 — yield 是一种完全不同的线程调度方法。不同于抢占式，可以由你自行控制何时发生切换：
from collections import deque
def countdown(n):
while n > 0:
yield n
n -=1
tasks = deque()
tasks.extend([countdown(10), countdown(5), countdown(20)])
def run():
while tasks:
task = tasks.popleft()
try:
x=next(task)
print(x)
tasks.append(task)
except StopIteration: print("Task")
This clever use of
yieldallows you to pause execution of a task and move onto a different task kind of like threading, except you, not the operating system are controlling how compute is interleaved.
Tip
- 学习了
Dockerfile和Jenkinsfile的语法，并以此构建了基建项目(s)的自动化部署