1.题目基本信息

1.1.题目描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1.2.题目地址

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

2.解题方法

2.1.解题思路

递归遍历 / 栈遍历

2.2.解题步骤

第一步，构建最小堆和维护变量。堆中的每个元素为(结点值,时间戳,结点)的元组形式，时间戳是为了防止结点值相同情况下结点对象不能比对的情况；timestamp维护时间戳；dumbNode维护哑结点，tail维护链表的尾部

第二步，不断从最小堆中弹出值最小的结点，并链接到链表尾部tail上，并将弹出结点的next结点压入堆中，直到堆为空

第三步，哑结点的next即为题解

3.解题代码

Python代码

import heapq

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from heapq import heapify, heappop, heappush

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 思路：最小堆
        # 第一步，构建最小堆和维护变量。堆中的每个元素为(结点值,时间戳,结点)的元组形式，时间戳是为了防止结点值相同情况下结点对象不能比对的情况；timestamp维护时间戳；dumbNode维护哑结点，tail维护链表的尾部
        heap = [(node.val, i, node) for i, node in enumerate(lists) if node is not None]
        heapify(heap)
        timestamp = len(lists)
        dumbNode = ListNode()
        tail = dumbNode
        # 第二步，不断从最小堆中弹出值最小的结点，并链接到链表尾部tail上，并将弹出结点的next结点压入堆中，直到堆为空
        while heap:
            val, _, node = heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next is not None:
                heappush(heap, (node.next.val, timestamp + 1, node.next))
                timestamp += 1
        # 第三步，哑结点的next即为题解
        return dumbNode.next

4.执行结果