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.

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

voiditer(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.

classSolution { public: TreeNode* increasingBST(TreeNode* root){ stack<TreeNode*> Q; TreeNode dummy; TreeNode* pre = &dummy; TreeNode* cur = root; if(root == NULL) returnNULL; 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; } };