树的遍历加强版-Morris算法

//本文转载于https://www.lularible.cn/blog/37//作者：lularible

抛砖引玉之“恢复二叉搜索树”

题目描述

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

来源：力扣（LeetCode）

链接：恢复二叉搜索树

解题思路

• 1.用递归的中序遍历，将树中结点值全部取出来存放到一个数组，再对数组进行排序，然后重新装回树中。这种办法很粗暴，时间复杂度为O（nlgn），空间复杂度为O（n），都很高。
• 1-1.对1做一点改进，将排序改为一趟遍历，当遇到比前一个小时，就找到了异常点，时间复杂度优化为O（n），但空间复杂度还是O（n）。
• 2.采用递归的中序遍历，用两个结点指针变量记录两个异常结点，一个前驱结点指针记录中序遍历的前驱结点，采用1-1的找异常点方法，获得两个异常结点指针，交换其中的值即可。时间复杂度为O（n），空间复杂度优化为O（h），h为树高。
• 3.采用Morris算法的中序遍历，还是用1-1中找异常点的办法，能将空间复杂度优化为O（1）。

普通的递归

class Solution {
public:
    void recoverTree(TreeNode* root) {
        //定义两个异常结点和前驱结点
        TreeNode* first = NULL,*second = NULL,*pre = NULL;
        inorderTree(root,first,second,pre);
        //交换两个异常结点的值
        int tmp = first->val;
        first->val = second->val;
        second->val = tmp;
    }

    void inorderTree(TreeNode* root,TreeNode*& first,TreeNode*& second,TreeNode*& pre){
        if(!root){
            return;
        }
        //先左
        if(root->left){
            inorderTree(root->left,first,second,pre);
        }
        //中间进行处理
        if(pre && root->val < pre->val){
            if(!first){
                first = pre;
                second = root;
            }
            else{
                second = root;
            }
        }
        pre = root;
        //再右
        if(root->right){
            inorderTree(root->right,first,second,pre);
        }
    }
};

Morris算法登场

具体操作

情况1：

当前结点cur无左孩子，继续遍历当前结点cur的右孩子

情况2：

当前结点cur有左孩子

情况2-1：

cur的左子树的最右结点的右结点为空，将cur的最右结点的右孩子指针指向cur，继续遍历cur的左孩子

情况2-2：

cur的左子树的最右结点的右结点不为空（即指向cur），则将这个指向置空，继续遍历cur的右孩子

遍历代码

参考链接：https://zhuanlan.zhihu.com/p/101321696

前序遍历

class Solution {
public:
    static void morrisPre(TreeNode* root) {
        if(!root){
            return;
        }
        TreeNode* cur = root;       //当前被访问的结点
        TreeNode* mostRight = NULL; //当前被访问结点的左孩子最右结点
        while(cur){
            mostRight = cur->left;
            //情况2：cur有左孩子
            if(mostRight){
                //条件判断中后一个是为了防止环循环
                while(mostRight->right && mostRight->right != cur){
                    mostRight = mostRight->right;
                }
                //情况2-1：最右结点右孩子为空
                if(!mostRight->right){
                    mostRight->right = cur;
                    cout << cur->val << " ";
                    cur = cur->left;
                }
                //情况2-2：最右结点右孩子指向cur
                else{
                    mostRight->right = NULL;
                    cur = cur->right;
                }
            }
            //情况1：cur无左孩子
            else{
                cout << cur->val << " ";
                cur = cur->right;
            }
        }
    }
};

中序遍历

class Solution {
public:
    static void morrisIn(TreeNode* root) {
        if(!root){
            return;
        }
        TreeNode* cur = root;       //当前被访问的结点
        TreeNode* mostRight = NULL; //当前被访问结点的左孩子最右结点
        while(cur){
            mostRight = cur->left;
            //情况2：cur有左孩子
            if(mostRight){
                //条件判断中后一个是为了防止环循环
                while(mostRight->right && mostRight->right != cur){
                    mostRight = mostRight->right;
                }
                //情况2-1：最右结点右孩子为空
                if(!mostRight->right){
                    mostRight->right = cur;
                    cur = cur->left;
                }
                //情况2-2：最右结点右孩子指向cur
                else{
                    mostRight->right = NULL;
                    cout << cur->val << " ";
                    cur = cur->right;
                }
            }
            //情况1：cur无左孩子
            else{
                cout << cur->val << " ";
                cur = cur->right;
            }
        }
    }
};

后续遍历

class Solution {
public:
    static void morrisPos(TreeNode* root) {
        if(!root){
            return;
        }
        TreeNode* cur = root;       //当前被访问的结点
        TreeNode* mostRight = NULL; //当前被访问结点的左孩子最右结点
        while(cur){
            mostRight = cur->left;
            //情况2：cur有左孩子
            if(mostRight){
                //条件判断中后一个是为了防止环循环
                while(mostRight->right && mostRight->right != cur){
                    mostRight = mostRight->right;
                }
                //情况2-1：最右结点右孩子为空
                if(!mostRight->right){
                    mostRight->right = cur;
                    cur = cur->left;
                }
                //情况2-2：最右结点右孩子指向cur
                else{
                    mostRight->right = NULL;
                    print(cur->left);
                    cur = cur->right;
                }
            }
            //情况1：cur无左孩子
            else{
                cur = cur->right;
            }
        }
        print(root);
    }

    //反序打印root、root->right、root->right->right......
    static void print(TreeNode* root){
        TreeNode* tail = reverseEdge(root);
        TreeNode* cur = tail;
        while(cur){
            cout << cur->val << " ";
            cur = cur->right;
        }
        reverseEdge(tail);
    }

    //将root、root->right、root->right->right......指针反向
    static void TreeNode* reverseEdge(TreeNode* root){
        TreeNode* pre = NULL;
        TreeNode* next = NULL;
        while(root){
            next = root->right;
            root->right = pre;
            pre = root;
            root = next;
        }
        return pre;
    }
};//本文转载于https://www.lularible.cn/blog/37//作者：lularible