[左程云]将搜索二叉树转换成双向链表[python][递归]

两种方法：借用一个容器如队列、递归解决。【本题python给的时间太少，单IO就超时，不用尝试使用Python求解了】

先给出一个本题构建树的IO方法：

# --BEG: INPUT AND BUILD TREE--- #
class Node:
    def __init__(self, x=None):
        self.v = x
        self.left = None
        self.right = None

def build_tree():
    n = int(input())
    nodes = [Node(i) for i in range(n + 1)]  # 节点的标号就是节点的值
    nodes[0] = None

    root_id = -1
    for i in range(n):
        fa, lch, rch = map(int, input().split())
        nodes[fa].left = nodes[lch]
        nodes[fa].right = nodes[rch]
        if root_id == -1:  # 确定根部节点
            root_id = fa
    return nodes[root_id]
# --END: INPUT AND BUILD TREE-- #

时间和空间复杂度都为N:

# --BEG:【方法一】中序输出-- #
def mid(node):
    if node is None:
        return
    mid(node.left)
    print(node.v, end=" ") # 可以适用于一个额外的容器保存节点然后构建双向链表即可，空间和时间复杂度都是N
    mid(node.right)
# mid(root), print()
# --END:【方法一】中序输出-- #

左程云的方法——process函数将一个树结构变成以下形式

对于多个节点，将其重构成如下形式，便完成了转双向链表的操作：

时间和空间复杂度分别为N和树高度：

# --BEG:【方法二】左程云-- #
def process(node):
    if node is None:
        return None
    le, re = process(node.left), process(node.right)
    if le and re:
        re.right.left = node
        node.right = re.right
        re.right = le.right
        node.left = le
        le.right = node
        return re
    elif le:
        node.left = le
        node.right = le.right
        le.right = node
        return node
    elif re:
        node.right = re.right
        re.right.left = node
        re.right = node
        return re
    else:  # 叶子节点自旋
        node.right = node
        return node

def convert(node):
    assert node
    last = process(node)
    head = last.right
    last.right = None
    return head
# --END:【方法二】左程云-- #