Coder's Cat

LeetCode: Increasing Order Search Tree

2020-11-20

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.

For example:

Input: root = [5,1,7]
Output: [1,null,5,null,7]

Recursive Traverse

For a binary search tree, in-order traverse will get a increased sequence. Recursive traverse will be easy, but we need to store previous node, update the previous node’s right child.

class Solution {
public:
TreeNode* cur = NULL;
TreeNode* head = NULL;
TreeNode* increasingBST(TreeNode* root) {
cur = NULL;
iter(root);
return head;
}

void iter(TreeNode* node) {
if(node->left) iter(node->left);
if(cur) {
cur->right = node;
cur = cur->right;
} else {
cur = node;
head = cur;
}
node->left = NULL;
if(node->right) iter(node->right);
}
};

Iterative version with stack

In-order traverse can also implemented with a stack.

class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
stack<TreeNode*> Q;
TreeNode dummy;
TreeNode* pre = &dummy;
TreeNode* cur = root;
if(root == NULL) return NULL;
while(!Q.empty() || cur) {
while(cur) {
Q.push(cur);
cur = cur->left;
}
cur = Q.top(); Q.pop();
pre->right = cur;
pre->left = NULL;
pre = cur;
cur = cur->right;
}
return dummy.right;
}
};