题解 | #二叉搜索树与双向链表#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    //二叉树的所有遍历方式中只有Morris遍历能做到空间复杂度为O（1）
    TreeNode*head=NULL,*pre=NULL;
    void Morris(TreeNode*root){
        if(root==NULL)
            return;
        TreeNode*cur=root;
        while(cur){
            TreeNode*mostRight=cur->left;
            if(mostRight!=NULL){//如果有左子树，找到左子树上的最右节点
                while(mostRight->right!=NULL&&mostRight->right!=cur){
                    mostRight=mostRight->right;
                }
                if(mostRight->right==NULL){//说明这是第一次遇到cur
                    mostRight->right=cur;
                    cur=cur->left;
                }
                else{//说明这是第二次遇到cur，应该打印cur
                    mostRight->right=NULL;
                    if(head==NULL){
                        head=cur;
                        pre=cur;
                    }
                    else{
                        pre->right=cur;
                        cur->left=pre;
                        pre=pre->right;
                    }
                    cur=cur->right;//cur向右移动
                }
            }
            else{//说明没有左子树，直接打印
                if(head==NULL){
                        head=cur;
                        pre=cur;
                    }
                    else{
                        pre->right=cur;
                        cur->left=pre;
                        pre=pre->right;
                    }
                cur=cur->right;
            }
        }
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        Morris(pRootOfTree);
        if(head){
        head->left=NULL;
        pre->right=NULL;
        }
        
        return head;
    }
};