897. Increasing Order Search Tree

Version #2 Iterative Version
二刷
Bug
MLE -> 一开始不知道咋回事，后来发现是一个edge case
   1
  /
2
由于我是prev.left = null
当root是最后一个点的时候，没有机会给prev.left设置成null
就会形成环

100.00 %
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode prev = null;
        TreeNode curr = root;
        TreeNode head = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {       
                stack.addFirst(curr);
                curr = curr.left;
            }
            curr = stack.removeFirst();
            if (head == null) {
                head = curr;
            }
            if (prev != null) {
                prev.right = curr;
                prev.left = null;
            }
            prev = curr;
            curr = curr.right;
        }
        prev.left = null;
        return head;
    }
}

一刷
64.21 %
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode result = null;
        TreeNode prev = null;
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev == null) {
                result = curr;
            } else {
                prev.right = curr;
            }
            prev = curr;
            curr.left = null;
            curr = curr.right;
        }
        return result;
    }
}



Version #1 Recursion
Key is the base case
When root == null, what should we return -> consider its parent node

22.36 %
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        return helper(root, null);
    }
    // result = increasingBST(root.left) + root + increasingBST(root.right)
    // return the head node and connect the last node of result to tail
    private TreeNode helper(TreeNode root, TreeNode tail) {
        if (root == null) {
            return tail;
        }
        TreeNode result = helper(root.left, root);
        root.left = null;
        root.right = helper(root.right, tail);
        return result;
    }
}