Published: Oct 14, 2022
The problem doesn’t require to return original node object. The brute force solution would be creating new nodes while traversing by an inorder manner. However, the better solution is there. While traversing, relink the nodes. When the traversal goes to left, the left subtree should be converted to linked list + current node. When the traversal goes to right, the right subtree should be converted to linked list + greater node.
rootof 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
0 <= Node.val <= 1000
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] Explanation: 5 --> 1 / \ \ 3 6 2 / \ \ \ 2 4 8 3 / / \ \ 1 7 9 4 \ 5 \ 6 \ 7 \ 8 \ 9
Example 2 Input: root = [5,1,7] Output: [1,null,5,null,7] Explanation: 5 ---> 1 / \ \ 1 7 5 \ 7
The increasing order of the binary search tree can get by inorder traversal. Visit left, do something, then visit right. When it goes to left or right child, bring the greater node with it. The left subtree’s greater node is a parent node. It returns linked list + current node. The right subtree’s greater node is the greater node so far. It returns linked list + greater node. When the recursive traversal is over, the answer is there.
# 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 IncreasingOrderSearchTree: def increasingBST(self, root: TreeNode) -> TreeNode: def helper(root, greater): if not root: return greater left = helper(root.left, root) root.left = None root.right = helper(root.right, greater) return left return helper(root, None)
O(h)– h: height of tree