vlambda博客
学习文章列表

合并的艺术2.0:合并链表、数组、二叉树

目录

合并的艺术2.0:合并链表、数组、二叉树

1 合并K个有序链表 (全)

2 合并有序数组

3 合并二叉树

合并的艺术2.0:合并链表、数组、二叉树

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 l2


1.2 合并后排序

class ListNode:
     def __init__(self, val=0next=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.next

合并的艺术2.0:合并链表、数组、二叉树

2 合并有序数组

合并有序数组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

合并的艺术2.0:合并链表、数组、二叉树


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(selft1: 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科研通,学习路上更轻松。