Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
The number of nodes in the given tree will be in the range [1, 100].
0 <= Node.val <= 1000
Solutions
Solution 1: DFS In-order Traversal
We define a virtual node $dummy$, initially the right child of $dummy$ points to the root node $root$, and a pointer $prev$ points to $dummy$.
We perform an in-order traversal on the binary search tree. During the traversal, each time we visit a node, we point the right child of $prev$ to it, then set the left child of the current node to null, and assign the current node to $prev$ for the next traversal.
After the traversal ends, the original binary search tree is modified into a singly linked list with only right child nodes. We then return the right child of the virtual node $dummy$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary search tree.
1 2 3 4 5 6 7 8 9101112131415161718192021
# 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 = rightclassSolution:defincreasingBST(self,root:TreeNode)->TreeNode:defdfs(root):ifrootisNone:returnnonlocalprevdfs(root.left)prev.right=rootroot.left=Noneprev=rootdfs(root.right)dummy=prev=TreeNode(right=root)dfs(root)returndummy.right
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcincreasingBST(root*TreeNode)*TreeNode{dummy:=&TreeNode{Val:0,Right:root}prev:=dummyvardfsfunc(root*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}dfs(root.Left)prev.Right=rootroot.Left=nilprev=rootdfs(root.Right)}dfs(root)returndummy.Right}