Morris中序遍历

Morris中序遍历
没有人给出莫里斯遍历的代码，我贴一个把，直接在原来的树上操作，时间复杂度O(n)，空间复杂度O(1)
莫里斯遍历算法：
判断当前结点cur的左子树是否为空：
a.如果为空，则令cur=cur->right;
b.如果不为空，则找到当前结点左子树的最右叶子节点mostright（也就是左子树的最大值结点）。判断mostright的右结点是否为cur,如果不是则将mostright->right = cur,相当于建立了一个连接；如果是则表示当前结点cur的左子树已经遍历完了，令cur=cur->right,去遍历cur的右子树。

题目要求建立双向链表，所以需要用一个指针记录当前遍历的结点的上一个结点，还需要一个指针记录双向链表的头结点，代码如下：

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr) return pRootOfTree;
        TreeNode* cur = pRootOfTree;
        TreeNode* mostright = nullptr;
        TreeNode* first =nullptr,*pre = nullptr;
        while(cur!=nullptr){
            if(cur->left!=nullptr){
                mostright = cur->left;
                while(mostright->right!=nullptr&&mostright->right!=cur){
                    mostright=mostright->right;//找到左子树的最右结点
                }
                if(mostright->right==nullptr){//建立最右结点与当前结点的连接
                    mostright->right = cur;
                    cur=cur->left;
                }else{//左子树遍历完了，遍历到当前结点
                    pre->right = cur;//建立当前结点与上一个结点的双向连接
                    cur->left = pre;
                    pre = cur;
                    cur = cur->right;
                }
            }
            else{
                if(first==nullptr) first = cur;//记录链表的头结点
                if(pre==nullptr) pre = cur; //初始化pre为头结点
                else {
                    pre->right = cur; //建立当前结点与上一个结点的双向连接
                    cur->left = pre;
                    pre = cur;
                }
                cur = cur->right;
            }
        }
        return first;
    }
};