Finally ended a few days of dynamic planning , Today is a simple question . But take a closer look , It seems that this simple problem related to trees is not so simple , At least for me . For so long , Little has been done on the subject of trees , Just take today to learn .

Title Description

Title address ： Incremental sequential search tree

Solution 1

The idea of solution one is relatively simple and direct , Is to traverse directly in middle order, and then store all elements in an array , Then take out the elements from the array and rebuild a tree .

# 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:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def dfs(root: TreeNode, ans: List) -> List:
            if root == None:return 
            dfs(root.left, ans)
            ans.append(root.val)  
            dfs(root.right, ans)
        nums = []
        dfs(root, nums)
        dummynode = TreeNode(-1)
        currentnode = dummynode
        for i in nums:
            currentnode.left = None
            currentnode.right = TreeNode(i)
            currentnode = currentnode.right
        return dummynode.right

Dumb nodes are used here again , Dumb nodes are very useful in many topics related to linked lists and trees , Some complicated boundary judgment can be omitted .

Solution 2

Solution 2 is also the method I first thought of , That is to directly change the pointer during the middle order traversal . But I didn't do it myself , Read the answer to understand how to do .

# 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:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        dummynode = TreeNode(-1)
        self.currentnode = dummynode
        self.dfs(root)
        return dummynode.right

    def dfs(self, node: TreeNode) -> List:
        if node == None:return 
        self.dfs(node.left)
        self.currentnode.right = node
        node.left = None
        self.currentnode = node
        self.dfs(node.right)