剑指 Offer 36. 二叉搜索树与双向链表

思路：中序遍历+双指针

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        stack<Node*> stk;
        while(root!=nullptr){
            stk.push(root);
            root=root->left;
        }
        Node* prev=nullptr,*head;
        while(stk.size()){
            Node* cur=stk.top();
            stk.pop();
            if(prev==nullptr)
                head=cur;
            else{
                prev->right=cur;
                cur->left=prev;
            }
            prev=cur;
            if(cur->right) {
                cur=cur->right;
                //注意要遍历所有的左子树
                while(cur!=nullptr){
                    stk.push(cur);
                    cur=cur->left;
                }
            }
        }
        prev->right=head;
        head->left=prev;
        return head;
    }
};

时间复杂度 O(N) N是二叉树的节点数

空间复杂度 O(N)

Morris中序遍历

流程如下：

1. 如果cur为空，停止遍历
2. 如果cur不为空：
   1. 如果cur的左节点为空，打印cur值，然后让cur指向右子节点
   2. 如果cur有左子节点，则让左子节点找到最右边的结点pre
      1. 如果pre的右子节点为空，让pre的右子节点指向cur，即pre->right=cur,然后cur指向左子节点，即cur=cur->left
      2. 如果pre的右子节点不为空，则让它指向空，即pre->right=nullptr,然后输出cur的值，并将cur指向右子节点，即cur=cur->right

具体可以看下二叉树的Morris中序和前序遍历

先序遍历和中序遍历只是访问结点的时机不同，先序遍历在步骤2访问左子树之前访问根节点，中序遍历在访问左子树后访问右子树前访问根节点，具体步骤如下：

1. 如果cur为空，停止遍历
2. 如果cur不为空：
   1. 如果cur的左节点为空，然后让cur指向右子节点
   2. 如果cur有左节点，则让左子节点找到最右边的结点pre
      1. 如果pre的右子节点为空，让pre的右子节点指向cur，打印cur值，然后cur指向左子节点
      2. 如果pre的右子节点不为空，则让它指向空，然后指向右子结点

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        Node* prev=nullptr,*cur=root,*head;
        while(cur!=nullptr){
            if(cur->left==nullptr){
                if(prev==nullptr){
                    head=cur;
                }else{
                    prev->right=cur;
                }
                cur->left=prev;
                prev=cur;
                cur=cur->right;
            }else{
                Node* preTree=cur->left;
                while(preTree->right!=nullptr&&preTree->right!=cur){
                    preTree=preTree->right;
                }
                if(preTree->right==nullptr){
                    preTree->right=cur;
                    cur=cur->left;
                }else{
                    preTree->right=nullptr;
                    prev->right=cur;
                    cur->left=prev;
                    prev=cur;
                    cur=cur->right;
                }
            }
        }
        head->left=prev;
        prev->right=head;
        return head;
    }
};

时间复杂度 O(n)

空间复杂度 O(1)