Свести бинарное дерево в связанный список в линейной сложности

Question

Я пытаюсь решить этот вопрос

Учитывая двоичное дерево, свести его к связанному списку на месте.

Мое рабочее решение:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


def append(node, x):
    prev = None 
    while node:
        prev = node 
        node = node.right
    prev.right =x 
    return prev 


def inorder(node):
    if node is None:
        return None 
    left = inorder(node.left)
    right = inorder(node.right)
    node.left= None
    node.right = left 
    if node.right:
        append(node.right, right)
    else:
        node.right = right 
    return node 

class Solution:
    def flatten(self, root: TreeNode) -> None:
        inorder(root)

У меня два вопроса

(1) Какова его временная сложность в худшем случае? Я думаю, что это n ^ 2, но я не уверен.

(2) Как мне оптимизировать это решение с точки зрения сложности времени?