乐趣区

关于二叉树:Morris遍历线索二叉树

jiezi

前言

自己作为左程云的学生，现将课程上的 morris 遍历内容进行演绎整顿，java 版本代码均为左老师课上代码，c++ 代码为自己间接改写，并均通过 leetcode 测试。

什么是 morris 遍历

morris 遍历是利用二叉树自身闲暇进去的指针 (n 个节点的二叉树有 n + 1 个指针闲暇) 来作为辅助变量实现二叉树的遍历的一种办法。Morris 遍历法能以 O(1)的空间复杂度和 O(n)的工夫复杂度实现二叉树的三种遍历, 其中不应用栈或额定空间。

morris 遍历流程

1、咱们应用 cur 指针指向以后结点，mostRight 指针指向 cur 左子树的最右结点，也即是 cur 的前驱结点
2、如果以后结点没有左子树，咱们让 cur 往右走
3、如果有左子树，那么找到其左子树的最右结点(原树中的最右结点，而不是批改过指针的最右结点，看到前面就分明了)，并应用 mostRight 保留。3.1、如果 mostRight 的右指针为空，(阐明此时是第一次来到 cur 所指向结点)，让 mostRight 的右指针指向 cur，而后让 cur 往左走。3.2、如果 mostRight 的右指针不为空，(阐明此时是第二次来到 cur 所指向结点)，让 mostRight 的右指针从新置为 null，而后 cur 往右走
4、如果以后结点为空，遍历进行(回退过程合并到往右走了)。
morris 遍历图解：










morris 序

在进行 morris 遍历的时候每次遍历都拜访该节点所取得的拜访程序就是 morris 序。在上述例子中的 morris 如下

1 2 4 2 5 1 3 6 3 7

能够看到有的节点拜访了两次有的节点只拜访了一次，依据这个特点咱们能够推导出 morris 的前序，中序和后序序列，并且这里得记住一个特点就是，只有有左孩子的节点才会被拜访两次，没有左孩子的只会拜访一次。

morris 序的代码实现

java 版本
public static class Node {
   public int value;
   Node left;
   Node right;

   public Node(int data) {this.value = data;} 
}

public static void morris(Node head) {if (head == null) {return;}
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) { // 有左树的状况下
            // 找到 cur 左树上，实在的最右
            while (mostRight.right != null && mostRight.right != cur) {mostRight = mostRight.right;}
            // 从 while 中进去，mostRight 肯定是 cur 左树上的最右节点
            // mostRight
            if (mostRight.right == null) {// 第一次来到 cur 结点
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else { // mostRight.right != null -> mostRight.right == cur
                mostRight.right = null;
            }
        }
        // 没有左子树或者第二次来到 cur 结点
        cur = cur.right;
    }
}
c++ 版本
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};
void morris(TreeNode* root){if(!root) return;
    TreeNode* cur=root;
    TreeNode* mostRight;
    while(cur){
        mostRight = cur->left;
        if(mostRight){
            // 有左子树
            while(mostRight->right&&mostRight->right!=cur){
                // 只有有右孩子并且右孩子不是以后结点
                mostRight = mostRight->right;
            }
            if(!mostRight->right){
                // mostRight 的右孩子为空，阐明是第一次拜访 cur
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }else{
                // mostRight 的右孩子为 cur，阐明是第二次来到 cur
                mostRight->right = nullptr;
            }
        }
        // 没有左子树或者第二次来到 cur 结点
        cur = cur->right;
    }
}

morris 先序遍历

先序遍历就是在 morris 遍历的时候在第一次遍历以后结点的时候进行输入即可，这里间接给出代码，会发现改变的中央就 2 处

java 版本
public static void morrisPre(Node head) {if (head == null) {return;}
    Node cur1 = head;
    Node cur2 = null;
    while (cur1 != null) {
        cur2 = cur1.left;
        if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}
            if (cur2.right == null) {
                cur2.right = cur1;
                System.out.print(cur1.value + " ");
                cur1 = cur1.left;
                continue;
            } else {cur2.right = null;}
        } else {System.out.print(cur1.value + " ");
        }
        cur1 = cur1.right;
    }
    System.out.println();}
c++ 版本
vector<int> result;// 保留先序遍历
void morris(TreeNode* root){if(!root) return;
    TreeNode* cur=root;
    TreeNode* mostRight;
    while(cur){
        mostRight = cur->left;
        if(mostRight){
            // 有左子树
            while(mostRight->right&&mostRight->right!=cur){
                // 只有有右孩子并且右孩子不是以后结点
                mostRight = mostRight->right;
            }
            if(!mostRight->right){
                // mostRight 的右孩子为空，阐明是第一次拜访 cur
                result.push_back(cur->val);
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }else{
                // mostRight 的右孩子为 cur，阐明是第二次来到 cur
                mostRight->right = nullptr;
            }
        }else{
            // 没有左子树，只会遍历一次，间接拜访
            result.push_back(cur->val);
        }
        // 没有左子树或者第二次来到 cur 结点
        cur = cur->right;
    }
}

morris 中序遍历

中序遍历就是在 morris 遍历的时候在第二次遍历以后结点的时候进行输入即可，这里同样间接给出代码，须要批改的中央就一处。

java 版本
public static void morrisIn(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;}
        }
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println();}
c++ 版本
vector<int> result;// 保留中序遍历后果
void morris(TreeNode* root){if(!root) return;
    TreeNode* cur=root;
    TreeNode* mostRight;
    while(cur){
        mostRight = cur->left;
        if(mostRight){
            // 有左子树
            while(mostRight->right&&mostRight->right!=cur){
                // 只有有右孩子并且右孩子不是以后结点
                mostRight = mostRight->right;
            }
            if(!mostRight->right){
                // mostRight 的右孩子为空，阐明是第一次拜访 cur
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }else{
                // mostRight 的右孩子为 cur，阐明是第二次来到 cur
                mostRight->right = nullptr;
            }
        }
        // 没有左子树或者第二次来到 cur 结点
        result.push_back(cur->val);
        cur = cur->right;
    }
}

morris 后序遍历

后序遍历的解决有点简单，因为没有哪个节点是遍历 3 次的，然而一样能够利用遍历 2 次的节点来解决，咱们应用的办法时在第二次来到以后节点时，将该节点的左子树的右边界进行逆序输入，直到左右有左子树的节点的左子树右边界均输入结束，最初再把根节点的左边边界进行逆序输入即可。说起来感觉有点形象，看上面的例子就好。

那么当初就只剩下一个问题了，morris 遍历是一个工夫复杂度为 O(n), 空间复杂度为 O(1)的算法，如何原地逆置任意节点的左子树的右边界呢？答案是单链表逆置，咱们在每一次须要逆序输入右边界的时候就应用单链表逆置的办法将右边界节点逆置，而后再从尾往前输入就好，输入结束后再逆置还原。
java 版本
public static 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);
    System.out.println();}
public static void printEdge(Node head) {Node tail = reverseEdge(head);
    Node cur = tail;
    while (cur != null) {System.out.print(cur.value + " ");
        cur = cur.right;
    }
    reverseEdge(tail);
}
public static 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;
}
c++ 版本
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};

vector<int> result;

TreeNode* reverseEdge(TreeNode* root){
    TreeNode* pre = nullptr;
    TreeNode* next = nullptr;
    while(root){
        next = root->right;
        root->right = pre;
        pre = root;
        root = next;
    }
    return pre;
}
void printRightEdge(TreeNode* root){TreeNode* tail = reverseEdge(root);// 取得逆置后的尾结点
    TreeNode* cur = tail;// 暂存尾结点作为工作节点，最初得从新逆置 tail 还原
    while(cur){result.push_back(cur->val);
        cur = cur->right;
    }
    reverseEdge(tail);
}
void morris(TreeNode* root){if(!root) return;
    TreeNode* cur = root;
    TreeNode* mostRight = nullptr;
    while(cur){
        mostRight = cur->left;
        if(mostRight){while(mostRight->right&&mostRight->right!=cur){mostRight = mostRight->right;}
            if(!mostRight->right){
                // 第一次遍历 cur 节点
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }else{
                mostRight->right = nullptr;
                printRightEdge(cur->left);
            }
        }
        // 没有左孩子或者第二次遍历到 cur 节点
        cur = cur->right;
    }
    // 最初解决根节点的右边界
    printRightEdge(root);
}
退出移动版