Morris遍历

1、核心区别

Morris遍历与普通遍历的区别在于，包括递归和迭代在内的普通遍历都是通过栈来实现节点的遍历当我们执行完对当前节点操作之后，我们将当前节点出栈从而获得上一个节点。不同于普通的遍历，Morris遍历通过修改树中未使用的节点的指针来指向他的上一个节点，从而不使用栈就能获得上一个节点，我们只需要维护常量个指针即可完成，因而将空间复杂度从O(n)降低到O(1)。

2、Morris遍历实现前序遍历

我们在进行Morris遍历时遵循以下几个步骤：
1、考虑到前序遍历中，我们按照“根左右”的顺序进行遍历，因此我们在遍历完左子树的节点想要回到根节点时，需要使用左子树中一个未使用的节点指针进行移动，因此在此时我们采用左子树中最右节点的右指针记录根节点；
2、若此时左子树中最右节点的右指针为空，我们将右指针指向当前的根节点，而后对根节点进行操作，之后将当前根节点的左子节点作为新的根节点；
3、若此时左子树中最右节点的右指针不为空，说明该右指针指向当前的根节点，此时当前根节点的左子树已经遍历完成，我们将右指针置为空还原先前树的形式，而后将当前根节点的右子节点作为新的根节点。
4、若当前根节点的左子树为空，我们对当前的根节点进行处理并将当前根节点的右子节点作为新的根节点。

class Solution{
public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        if(root==nullptr)
        return res;
        TreeNode* cur=root, *pre=nullptr;
        while(cur!=nullptr){
            if(cur->left==nullptr){
                res.push_back(cur->val);
                cur=cur->right;
            }
            else{
                pre=cur->left;
                while(pre->right!=nullptr && pre->right!=cur){
                    pre=pre->right;
                }
                if(pre->right==nullptr){
                    pre->right=cur;
                    res.push_back(cur->val);
                    cur=cur->left;
                }
                if(pre->right==cur){
                    pre->right=nullptr;
                    cur=cur->right;
                }
            }
        }
        return res;
    }
};
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

3、Morris遍历实现中序遍历

核心思想与前序遍历相同，区别在于对根节点进行操作的时间点不同。

class Solution{
public:
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> res;
        if(root==nullptr)
        return res;
        TreeNode* cur=root, *pre=nullptr;
        while(cur!=nullptr){
            if(cur->left==nullptr){
                res.push_back(cur->val);
                cur=cur->right;
            }
            else{
                pre=cur->left;
                while(pre->right!=nullptr && pre->right!=cur){
                    pre=pre->right;
                }
                if(pre->right==nullptr){
                    pre->right=cur;
                    cur=cur->left;
                }
                if(pre->right==cur){
                    pre->right=nullptr;
                    res.push_back(cur->val);
                    cur=cur->right;
                }
            }
        }
        return res;
    }
};

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

4、Morris遍历实现后序遍历

考虑到后续遍历的顺序是“左右中”，因此我们只是用cur指针不能同时确定右节点和根节点的位置。因此我们在遍历完左子树的所有节点之后，可以通过cur指针回到其对应的根节点，而后将根节点的下一层中所有左节点的右子节点以此遍历而后逆序输出。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr)
        return res;
        TreeNode* cur=root,*pre=nullptr;
        while(cur!=nullptr){
            if(cur->left==nullptr){
                cur=cur->right;
            }
            else{
                pre=cur->left;
                while(pre->right!=nullptr && pre->right!=cur){
                    pre=pre->right;
                }
                if(pre->right==nullptr){
                    pre->right=cur;
                    cur=cur->left;
                }
                if(pre->right==cur){
                    pre->right=nullptr;
                    rightBrunch(cur->left,res);
                    cur=cur->right;
                }
            }
        }
        rightBrunch(root,res);
        return res;
    }
    void rightBrunch(TreeNode* root , vector<int>& res){
        TreeNode* cur=root;
        int count=0;
        while(cur!=nullptr){
            ++count;
            res.push_back(cur->val);
            cur=cur->right;
        }
        reverse(res.end()-count,res.end());
    }
};

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