【转载】树的遍历加强版-Morris算法

技术贴分享 转载 精帖
0 12
admin
admin 官方人员 2021-02-12 10:05:40
用户等级:10000级

树的遍历加强版-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

楼主签名:ZW社区官方
回帖
回复列表