Morris遍历

一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)

通过利用原树中大量空闲指针的方式，达到节省空间的目的

Morris遍历可以改前中后序的树遍历

思路：

创建一个当前节点cur 等于 head节点，再创建一个mostRight节点 表示最右节点

mostRight 当为空的时候表示是第一次来，如果mostRight 指向的是 cur 节点的位置，则代表已经来过一次了，现在是第二次，第二次来的时候直接mostRight置空就可以了

总流程是，当 cur 不为空的时候，mostRight 来到左孩子的位置，如果右孩子存在且是第一次来到这个节点，mostRight 遍历到最后

然后再判断，当前节点的右孩子是否为空，如果是空就把 mostRight 的右孩子指向 cur ，表示自己已经来过了一次，然后 cur 来到他左孩子的位置，继续循环的找。

如果当 cur 来到了 最右结点，发现右孩子是被修改过的，也就是之前修改成cur的指针，然后 cur 就会回到上次的 cur 的位置，回去之后，再把刚刚的那个结点右孩子改为空

就像一个线索一样，不断的执行这些过程，直到完成整个遍历

class Node
{
public:
    Node(int data) :value(data){}
    int value;
    Node *left;
    Node *right;
};

void morris(Node *head)
{
    if (head == NULL)
    {
        return;
    }
    Node *cur = head;
    Node *mostRight = NULL;
    while (cur != NULL)
    {
        mostRight = cur->left;
        if(mostRight != NULL)
        {
            while(mostRight->right != NULL && mostRight->right != cur)
            {
                mostRight = mostRight->right;
            }
            if (mostRight->right == NULL)
            {
                mostRight->right = cur;
                cout << cur->value << " ";
                cur = cur->left;
                continue;
            }
            else {
                mostRight->right = NULL;
            }
        }
        cout << cur->value << " ";
        cur = cur->right;
    }
}

 

Morris改先序遍历

思路：

先序遍历的打印结果只需要把第一次遍历到的位置都输出，也就是除了第二次来到的位置都打印，就是先序遍历

void morrisPre(Node *head)
{
    if (head == NULL)
    {
        return;
    }
    Node *cur = head;
    Node *mostRight = NULL;
    while (cur != NULL)
    {
        mostRight = cur->left;
        if (mostRight != NULL)
        {
            while (mostRight->right != NULL && mostRight->right != cur)
            {
                mostRight = mostRight->right;
            }
            if (mostRight->right == NULL)
            {
                mostRight->right = cur;
                //第一次来了，直接返回上去
                cout << cur->value << " ";
                cur = cur->left;
                continue;
            }
            else {
                //第二次来到的
                mostRight->right = NULL;
            }
        }
        else {
            //第一次来到的
            cout << cur->value << " ";
        }
        cur = cur->right;
    }
}

 

 

Morris改中序遍历

思路：

中序遍历，只需要把 能第二次来到的位置，第二次打印出来，第一次不打印，然后把只能来一次的位置第一次打印出来，就是中序遍历

void morrisMid(Node *head)
{
    if (head == NULL)
    {
        return;
    }
    Node *cur = head;
    Node *mostRight = NULL;
    while (cur != NULL)
    {
        mostRight = cur->left;
        if (mostRight != NULL)
        {
            while (mostRight->right != NULL && mostRight->right != cur)
            {
                mostRight = mostRight->right;
            }
            if (mostRight->right == NULL)
            {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {
                mostRight->right = NULL;
            }
        }
        cout << cur->value << " ";
        cur = cur->right;
    }
}

 

Morris后序遍历

思路：

把能进行二次遍历的结点 的右子树 逆序打印，最后再将 整个的右子树 逆序打印

Node* reverseEdge(Node *from)
{
    Node *pre = NULL;
    Node *next = NULL;
    while (from != NULL)
    {
        next = from->right;
        from->right = pre;
        pre = from;
        from = next;
    }
    return pre;
}

void printEdge(Node *head)
{
    Node *tail = reverseEdge(head);
    Node *cur = tail;
    while (cur != NULL)
    {
        cout << cur->value << " ";
        cur = cur->right;
    }
    reverseEdge(tail);
}

void morrisPos(Node *head)
{
    if (head == NULL)
    {
        return;
    }
    Node *cur = head;
    Node *mostRight = NULL;
    while (cur != NULL)
    {
        mostRight = cur->left;
        if (mostRight != NULL)
        {
            while (mostRight->right != NULL && mostRight->right != cur)
            {
                mostRight = mostRight->right;
            }
            if (mostRight->right == NULL)
            {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {
                mostRight->right = NULL;
                printEdge(cur->left);
            }
        }
        cur = cur->right;
    }
    printEdge(head);
}