Wrong solution(create a new tre is not allowded) but easy to understand :
# 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:
# time O(N) sapace O(N)
def increasingBST(self, root: TreeNode,tail=None) -> TreeNode:
#create dummy node and pointer node
dummy = cur = TreeNode(None)
# create global res list to store values
res = []
# typical inorder traverse
def dfs(node,res):
if not node:
return
dfs(node.left,res)
res.append(node.val)
dfs(node.right,res)
# after
dfs(root,res)
for val in res:
cur.right = TreeNode(val)
cur = cur.right
return dummy.right
correct solution :
# 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:
# time O(N) space O(H) H for stack recursion depth
def increasingBST(self, root: TreeNode) -> TreeNode:
def inorder(node):
if node:
#print(f'{node.val}, {node.left.val if node.left else None} ')
inorder(node.left)
node.left = None
self.cur.right = node
self.cur = node # cur ptr move to next
inorder(node.right)
res = self.cur = TreeNode(None)
inorder(root)
return res.right
same idea, simpler code
# 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,tail=None) -> TreeNode:
if not root: return tail
res = self.increasingBST(root.left,root)
root.left = None
#print(root.val,tail.val if tail else None if root else None)
root.right = self.increasingBST(root.right,tail)
return res
# 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:
res = self.cur = TreeNode(None)
def inorder(node):
if not node:
return
#print(f'{node.val}, {node.left.val if node.left else None} ')
inorder(node.left)
# cut current connection, otherwise create a circle
node.left = None
self.cur.right = node
self.cur = self.cur.right # cur ptr move to next
inorder(node.right)
inorder(root)
return res.right