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

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);
    }
};