合并的艺术2.0：合并链表、数组、二叉树
目录
1 合并K个有序链表 (全)
2 合并有序数组
3 合并二叉树
1 合并K个有序链表
好了，那现在请你将多个链表合并到一个升序链表中，返回合并后的链表
示例1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
1->4->5,
1->3->4,
2->6
👇
1->1->2->3->4->4->5->6
示例2：
输入：lists = [] 或 [[]]
输出：[]
1.1 回顾上篇文章方法——分治
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
return self.merge(lists, 0, len(lists) - 1)
def merge(self, lists, left, right):
# 分治：归并的思路
if left == right:
return lists[left]
elif left > right:
return None
else:
mid = (left + right) // 2
return self.mergeTwoLists(self.merge(lists, left, mid), self.merge(lists, mid + 1, right))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 最小子问题：合并2个链表
if not l1:
return l2
elif not l2:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l21.2 合并后排序
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists):
nums = []
for node in lists:
while node: # 直接用while node就可以
nums.append(node.val)
node = node.next
nums.sort()
p = head = ListNode(0) # 虚拟头节点
for value in nums:
p.next = ListNode(value) # 固定流程
p = p.next
return head.next2 合并有序数组
合并有序数组A和B，元素个数分别为m，n
2.1 一行搞定
class Solution:
def merge(self, A, m, B, n):
A[:] = sorted(A[:m]+B2)
2.2 设置哨兵： Infinity—— ∞
class Solution:
def merge(self, A, m, B, n):
A_copy = A[:m]
A[:] = []
A_copy.append(float('inf'))
B.append(float('inf'))
i = j = 0
for k in range(m + n):
if A_copy[i] < B[j]:
A.append(A_copy[i])
i += 1
else:
A.append(B[j])
j += 1
3 合并二叉树
合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。示例：
3.1 深度优先搜索：
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1:
return t2
if not t2:
return t1
t = TreeNode(t1.val + t2.val)
t.left = self.mergeTrees(t1.left, t2.left)
t.right = self.mergeTrees(t1.right, t2.right)
return t
3.2 广度优先搜索：
掌握BFS的思路后，并不复杂
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1: return t2
if not t2: return t1
merged = TreeNode(t1.val + t2.val)
# deque 是双边队列（double-ended queue），具有队列和栈的性质
queue = collections.deque([merged])
que1 = collections.deque([t1])
que2 = collections.deque([t2])
while que1 or que2:
# merged永远指向根，node则负责遍历
node = queue.popleft()
node1 = que1.popleft()
node2 = que2.popleft()
left1, right1 = node1.left, node1.right
left2, right2 = node2.left, node2.right
if left1 or left2:
if left1 and left2:
node.left = TreeNode(left1.val + left2.val)
queue.append(node.left)
que1.append(left1)
que2.append(left2)
elif left1:
node.left = left1
elif left2:
node.left = left2
if right1 or right2:
if right1 and right2:
node.right = TreeNode(right1.val + right2.val)
queue.append(node.right)
que1.append(right1)
que2.append(right2)
elif right1:
node.right = right1
elif right2:
node.right = right2
return merged
Hello BU learner
欢迎关注我，一起学习，一起进步!
跟着BU科研通，学习路上更轻松。