897. Increasing Order Search Tree
1. Description
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.
2. Example
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]
Example 2:
Input: root = [5,1,7]
Output: [1,null,5,null,7]
3. Constraints
- The number of nodes in the given tree will be in the range [1, 100].
- 0 <= Node.val <= 1000
4. Solutions
In-Order Traverse
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
TreeNode *increasingBST(TreeNode *root) {
traverse_(root);
iter_->left = iter_->right = nullptr;
return result_;
}
private:
TreeNode *result_ = nullptr;
TreeNode *iter_ = nullptr;
void traverse_(TreeNode *root) {
if (root != nullptr) {
traverse_(root->left);
if (result_ == nullptr) {
iter_ = result_ = root;
} else {
iter_->left = nullptr;
iter_->right = root;
iter_ = root;
}
traverse_(root->right);
}
}
};