Skip to main content

897. Increasing Order Search Tree

https://leetcode.com/problems/increasing-order-search-tree/

Python​

Inorder travel & rebuild​

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def inorder(node):
            if not node:
                return
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)

        dummy = TreeNode()
        cur = dummy
        for value in inorder(root):
            cur.right = TreeNode(val=value)
            cur = cur.right

        return dummy.right

Inorder travel with pointers swap​

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        dummy = TreeNode()
        cur = dummy

        def inorder(node):
            nonlocal cur
            if not node:
                return

            inorder(node.left)

            node.left = None
            cur.right = node
            cur = node

            inorder(node.right)

        inorder(root)
        return dummy.right