剑指Offer - 面试题36. 二叉搜索树与双向链表（中序循环/递归）

1. 题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

2. 解题

• 中序遍历
• 循环解法

循环写法总结如下：

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root)
            return NULL;
        bool foundHead = false;
        Node* head, *prev = NULL;
        stack<Node*> s;
        while(root || !s.empty())
        {
            while(root)
            {
                s.push(root);
                root = root->left;
            }
            if(!foundHead)
            {
                head = s.top();
                foundHead = true;
            }
            root = s.top()->right;
            
            if(prev)
                prev->right = s.top(); 
            s.top()->left = prev;
            prev = s.top();
            s.pop();
        }
        head->left = prev;//prev存的是最后一个
        prev->right = head;
        return head;
    }
};

-递归解法

class Solution {
    Node *head = NULL, *prev = NULL, *tail = NULL;
public:
    Node* treeToDoublyList(Node* root) {
        if(!root)
            return NULL;
        inorder(root);
        head->left = tail;
        tail->right = head;
        return head;
    }
    void inorder(Node* root)
    {
        if(!root)
            return;
        inorder(root->left);
        if(!prev)
            head = root;
        else
            prev->right = root;
        root->left = prev;
        prev = root;
        tail = root;
        inorder(root->right);
    }
};