'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    # construct the answer on the fly
    # reusing the nodes of the given tree by cutting their left child and
    # adjoining them to the answer.
    # T: O(N); S: O(H)
    def increasingBST1(self, root: TreeNode) -> TreeNode:
        def inorder(node):
            if node:
                inorder(node.left)
                node.left = None
                self.cur.right = node
                self.cur = node
                inorder(node.right)

        dummy = self.cur = TreeNode(None)
        inorder(root)
        return dummy.right
    
    
    # self-made; O(N) for S and T
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def inorder(node):
            return inorder(node.left) + [node.val] + inorder(node.right) if node else []
            
        vals = inorder(root)[::-1]
        val = vals.pop()
        pre = dummy = TreeNode(val)
        while vals:
            val1 = vals.pop()
            nxt = TreeNode(val1)
            pre.right = nxt
            pre = nxt
        return dummy