看起来很难，但是仔细想一下，实质就是二叉树的中序遍历的问题，中序遍历有递归和非递归(至少两种写法)。

递归：

class Solution {public:    Node *prev; //实质是指向最后一个元素的指针        Node* treeToDoublyList(Node* root) {        if (root==NULL) return NULL;        Node *dummy=new Node(0,NULL,NULL);        prev = dummy;        inorder(root);                prev->right = dummy->right;        dummy->right->left = prev;        return dummy->right;    }        void inorder(Node *root){        if (root==NULL) return;        inorder(root->left);        prev->right = root;        root->left = prev;        prev = root;        inorder(root->right);    }};

 

非递归

class Solution {public:    Node *prev; //实质是指向最后一个元素的指针        Node* treeToDoublyList(Node* root) {        if (root==NULL) return NULL;                stack
     
       s;        Node *dummy=new Node(0,NULL,NULL);        Node *p=root, *prev=dummy;                while (!s.empty() || p!=NULL){            while (p){                s.push(p);                p = p->left;            }            p = s.top(), s.pop();                            prev->right = p;            p->left = prev;            prev = p;                            p = p->right;        }                prev->right = dummy->right;        dummy->right->left = prev;                return dummy->right;    }};
     

 

class Solution {public:    Node *prev; //实质是指向最后一个元素的指针        Node* treeToDoublyList(Node* root) {        if (root==NULL) return NULL;                Node *dummy=new Node(0,NULL,NULL);        Node *prev=dummy;                stack
     
       s({root});        unordered_map
      
        hash;        while (!s.empty()){            Node *cur=s.top(); s.pop();            if (hash[cur]==0){                ++hash[cur];                s.push(cur);                if (cur->left) s.push(cur->left);            }else{                prev->right = cur;                cur->left = prev;                prev = cur;                                if (cur->right) s.push(cur->right);            }        }                prev->right = dummy->right;        dummy->right->left = prev;                return dummy->right;    }};
      
     

 

Divide and Conquer

思路和中序遍历很类似，但是代码写起来有一点不一样。感觉这种方法思路更加清晰。

class Solution {public:    Node* treeToDoublyList(Node* root) {        if (root==NULL) return NULL;        Node *leftHead=treeToDoublyList(root->left);        Node *rightHead=treeToDoublyList(root->right);        root->left = root; root->right = root; // make root a doublylist        return link(link(leftHead, root),rightHead);    }        Node *link(Node *head1, Node *head2){        if (head1==NULL) return head2;        if (head2==NULL) return head1;                Node *tail1=head1->left;        Node *tail2=head2->left;                tail1->right = head2;        head2->left = tail1;                tail2->right = head1;        head1->left = tail2;                return head1;    }};