Convert BST to Sorted Doubly-Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

https://articles.leetcode.com/convert-binary-search-tree-bst-to/

https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/544/

Solution 1: Recursive O(n); O(h)

    4
   / \
  2   5
 / \
1   3

    TreeNode head = null, prev = null;
    public TreeNode recursiveBSTtoCircularDL(TreeNode root) {
        convert(root);
        return head;
    }
    public void convert(TreeNode root) {
        // recursion的base case
        if (root == null) return;
        // inorder因为要从最左的child开始，所以DFS到最左
        convert(root.left);
        // root和prev连起来，第一个执行下面代码的是节点1（看上图），
        root.left = prev;
        // 如果prev不是null，说明不是head，prev和root连起来
        if (prev != null) prev.right = root;
        // 如果prev是null，说明是head，指向root，1是head
        else head = root;
        // 先把right存起来，接下来要改变
        TreeNode right = root.right;
        // 因为是inorder traversal, 总是让head.left指向current，即目前的最后一个
        head.left = root;
        // root.right同上
        root.right = head;
        // update prev
        prev = root;
        // inorder是左中右，所以右边最后价差
        convert(right);
    }

Solution 2: Iterative O(n); O(h)

    public static TreeNode iterativeBSTtoCircularDL(TreeNode root) {
        TreeNode head = null, prev = null;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left; // inorder，先到最左
            }
            root = stack.pop();
            root.left = prev;
            if (prev != null) prev.right = root;
            else head = root;
            TreeNode right = root.right;
            head.left = root;
            root.right = head;
            prev = root;
            root = right; // inorder, right最后
        }
        return head;
    }

Follow Up:

1.convert sorted list back to BST

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        return helper(head, null);
    }

    private TreeNode helper(ListNode head, ListNode tail) {
        if (head == tail) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode node = new TreeNode(slow.val);
        node.left = helper(head, slow);
        node.right = helper(slow.next, tail);
        return node;
    }