897. Increasing Order Search Tree

// LeetCode URL: https://leetcode.com/problems/increasing-order-search-tree/

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * Iterative Solution
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Number of nodes in the tree.
 */
class Solution1 {
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode dummy = new TreeNode(0);
        dummy.right = root;
        TreeNode pre = dummy;
        TreeNode cur = root;

        while (cur != null) {
            if (cur.left != null) {
                TreeNode tmp = cur.left;
                while (tmp.right != null) {
                    tmp = tmp.right;
                }
                tmp.right = cur;
                pre.right = cur.left;
                cur.left = null;
                cur = pre.right;
            } else {
                pre = cur;
                cur = cur.right;
            }
        }

        return dummy.right;
    }
}

/**
 * Iterative Solution
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(Height of the tree). In worst case O(N)
 *
 * N = Number of nodes in the tree.
 */
class Solution2 {
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode dummy = new TreeNode(0);
        dummy.right = root;

        TreeNode[] curSolved = new TreeNode[1];
        curSolved[0] = dummy;

        inorderHelper(root, curSolved);

        return dummy.right;
    }

    private void inorderHelper(TreeNode node, TreeNode[] curSolved) {
        if (node == null) {
            return;
        }
        inorderHelper(node.left, curSolved);
        curSolved[0].right = node;
        curSolved[0] = curSolved[0].right;
        node.left = null;
        inorderHelper(node.right, curSolved);
    }
}