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.

Let's take the following BST as an example, it may help you understand the problem better:

image

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

image

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

image

Solution

1. 题目给的是Binary Search Tree，所以用tree rotation的方法，从root开始对每个有left node的node进行right rotate，将树展开成链式。tree rotation介绍：https://www.youtube.com/watch?v=q4fnJZr8ztY
2. 在遍历的过程中，需要记录parent node and current node，将parent node. right = current node, 然后current node. left = parent node
3. 同时，需要记录展开以后的head node和tail node，将其链接，最后返回head node。
4. Corner Case: (1). Tree is null. (2) Tree only contains one node

Code

// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
    public Node treeToDoublyList(Node root) {
        // corner case: root is null or only has one node
        if (root == null)
        {
            return root;
        }
        
        if (root.right == null && root.left == null)
        {
            root.left = root;
            root.right = root;
            
            return root;
        }
        
        Node parent = null;
        Node head   = null;
        
        // Traverse the whole tree
        while (root != null)
        {
            // keep rotating the root which has left node
            // make it a list which only has right node
            while (root.left != null)
            {
                root = rotate (root);
            }
            
            // updating the new head node
            if (parent == null)
            {
                head = root;
            }
            
            // make it a doubly linked list
            root.left = parent;
            if (parent != null)
            {
                parent.right = root;
            }
            
            // move parent and root node
            parent = root;
            root   = root.right;
        }
        
        // connect tail and head
        parent.right = head;
        head.left = parent;
        
        return head;
    }
    
    public Node rotate (Node root)
    {
        Node oldLeft = root.left;
        Node oldRightOfLeft = oldLeft.right;
        
        oldLeft.right = root;
        oldLeft.right.left = oldRightOfLeft;
        
        return oldLeft;
    }
}