| DataStructure, Algorithm

Morris遍历

  • Morris 遍历时间复杂度 O(n)，空间复杂度 O(1)。
  • 改写 Morris 遍历实现二叉树的前中后序遍历。

令 cur 为当前结点：

  • 当前结点无左子树，cur 向右移动；

  • 当前结点有左子树，找到当前结点左子树最右的结点 mostRight

    i) 若mostRight->right = NULL ，令mostRight->right = cur，cur向左移动

    ii) 若mostRight->right = cur，令若mostRight->right = NULL，cur向右移动

1
2
3
4
5
6
7
8
9
10
//递归版本的遍历本质
void traversal(Node *head){
    if(head == NULL)
    	return;
    // 1  cout << head->value; pre
    traversal(head->left);
    // 2  cout << head->value; mid
    traversal(head->right);
    // 3  cout << head->value; post
}

递归的遍历即是3次来到当前节点的过程

morris 遍历

对于二叉树上的一个结点，如果它有左子树就会来到当前结点2次。如果当前结点没有左子树，则回来到该结点一次。利用左子树上最右结点的指向（NULL/CUR）来标记是第一次或是第二次达到该结点。由于每个节点都到达2次，时间复杂度为 O(n)，只用了额外的2个变量，空间复杂度为 O(1)。

遍历实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void MorrisTraversal(node *head){
    if (head == NULL)
        return;
    node *cur = head;
    node *mostRight = NULL;
    while(cur != NULL){
        mostRight = head->left;
        if(mostRight != NULL){
            while(mostRight->right != NULL && mostRight->right != cur){
                mostRight = mostRight->right;
            }
            //mostRight has been the most right node of head->left
            if(mostRight == NULL){//第一次达到该结点
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }else{//第二次到达该结点
                mostRight->right = NULL;
            }
        }
        cur = cur->right;
    }
}

Morris实现先序、中序和后序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void MorrisPre(node *head){
    if (head == NULL)
        return;
    node *cur = head;
    node *mostRight = NULL;
    while(cur != NULL){
        mostRight = head->left;
        if(mostRight != NULL){
            while(mostRight->right != NULL && mostRight->right != cur){
                mostRight = mostRight->right;
            }
            //mostRight has been the most right node of head->left
            if(mostRight == NULL){//第一次达到该结点
                mostRight->right = cur;
                cout << cur->val;//有左子树的结点，第一次到达时打印
                cur = cur->left;
                continue;
            } else{//第二次到达该结点
                mostRight->right = NULL;
            }
        } else{
            cout << cur->val;//没有左子树的结点直接打印
        }
        cur = cur->right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void MorrisIn(node *head){
    if (head == NULL)
        return;
    node *cur = head;
    node *mostRight = NULL;
    while(cur != NULL){
        mostRight = head->left;
        if(mostRight != NULL){
            while(mostRight->right != NULL && mostRight->right != cur){
                mostRight = mostRight->right;
            }
            //mostRight has been the most right node of head->left
            if(mostRight == NULL){//第一次达到该结点
                mostRight->right = cur;
                cur = cur->left;
                continue;
            } else{//第二次到达该结点
                mostRight->right = NULL;
            }
        } 
            cout << cur->val;//只有结点第二次到达以及结点无左子树才会进行到这一步
       	    cur = cur->right;
    }
}

后序相对复杂一些：核心思想即第二次达到自己时打印左子树上的右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void MorrisPost(node *head){
    if (head == NULL)
        return;
    node *cur = head;
    node *mostRight = NULL;
    while(cur != NULL){
        mostRight = head->left;
        if(mostRight != NULL){
            while(mostRight->right != NULL && mostRight->right != cur){
                mostRight = mostRight->right;
            }
            //mostRight has been the most right node of head->left
            if(mostRight == NULL){//第一次达到该结点
                mostRight->right = cur;
                cur = cur->left;
                continue;
            } else{//第二次到达该结点
                mostRight->right = NULL;
                printEdge(cur->left);//当结点第二次来到自己时，打印其左子树的右边界
            }
        } 
        cur = cur->right;
    }
    printEdge(head);//打印整棵树的右边界
}
void printEdge(node *head){
    node *tail = reverse(head);
    node *cur = tail
    while(cur != NULL){
        cout << cur->val;
        cur = cur->right;
    }
    reverseEdge(tail);
}
void reverseEdge(node *head){
    if(head == NULL)
    return head;
    node *pre = NULL;
    node *cur = head;
    node *next = NULL;
    while(cur != NULL){
    next = next->right;
    cur->right = pre;
    pre = cur;
    cur = next;
    }
    return pre;
}
ESC