requirements

Given a binary search tree, rearrange it in ascending order by traversing it in middle order, so that the leftmost node in the tree becomes the root node of the tree, and each node has no left child and only one right child.

Example 1:

Input: root = [5,3,6,2,4, null, 8, 1, null, null, null, 7, 9] output: [1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 7, null, 8, null, 9]Copy the code

Example 2:

Input: root = [5,1,7] output: [1, NULL,5, NULL,7]Copy the code

The core code


class TreeNode:
    def __init__(self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        preorder = list(a)def pre_order(root) :
            if not root:
                return 
            pre_order(root.left)
            preorder.append(root.val)
            pre_order(root.right)
        
        pre_order(root)

        dummp = TreeNode(0)
        for i,node in enumerate(preorder):
            temp = TreeNode(node)
            temp.left = None
            temp.right = None
            if i == 0:
                dummp.right = temp
                cur = temp
            else:
                cur.right = temp
                cur = temp
        return dummp.right
Copy the code

We use the middle order traversal to get an order of the list, and then we build a full-right tree as required.