Convert Binary Search Tree to Doubly Linked List

Convert a binary search tree to doubly linked list with in-order traversal.

http://www.lintcode.com/en/problem/convert-binary-search-tree-to-doubly-linked-list/

Discussion

就是in-order traversal。为节省空间，用Morris。

class Solution {
public:
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    DoublyListNode* bstToDoublyList(TreeNode* root) {
        if(root == NULL) return NULL;
        TreeNode *cur = root;
        DoublyListNode *head = NULL;
        DoublyListNode *tail = NULL;
        while(cur) {
            if(cur->left == NULL) {
                //cout cur, move right
                insertList(head, tail, cur->val);
                cur = cur->right;
            } else {
                TreeNode *tmp = cur->left;
                while(tmp->right && tmp->right != cur) {
                    tmp = tmp->right;
                }
                if(tmp->right == NULL) {
                    tmp->right = cur;
                    cur = cur->left;
                } else {//second time visiting cur, output
                    insertList(head, tail, cur->val);
                    tmp->right = NULL;
                    cur = cur->right;
                }
            }
        }
        return head;
    }
    void insertList(DoublyListNode* &head, DoublyListNode* &tail, int val) {
        if(head == NULL) {
            head = new DoublyListNode(val);
            tail = head;
        } else {
            DoublyListNode *newnode = new DoublyListNode(val);
            tail->next = newnode;
            newnode->prev = tail;
            tail = newnode;
        }
    }
};