Morris遍历

基本模板

注意业务逻辑书写的位置：
一般为：第一次访问节点。第二次访问节点。右子树为空。遍历完成。

/**
 * Morris遍历 模板
 */
public void morris(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        // cur 左子树不为空
        if (cur.left != null) {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // 第一次访问 cur
                // ... do something
                mostRight.right = cur;
                cur = cur.left;
            } else {
                // 第二次访问 cur
                // ... do something
                mostRight.right = null;
                cur = cur.right;
            }
        } else {
            // cur 左子树为空
            // ... do something
            cur = cur.right;
        }
    }
    // 遍历完成时
}

Morris - 前序

规则：
如果一个节点只能被访问一次，被访问时打印。
如果一个节点能被访问两次，在第一次被访问时打印。

代码

public void morrisNLR(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        // cur 左子树不为空
        if (cur.left != null) {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // 第一次访问 cur
                System.out.println(cur.val);
                // ... do something
                mostRight.right = cur;
                cur = cur.left;
            } else {
                // 第二次访问
                mostRight.right = null;
                cur = cur.right;
            }
        } else {
            // cur 左子树为空
            System.out.println(cur.val);
            // ... do something
            cur = cur.right;
        }
    }
}

Morris - 中序

规则：
如果一个节点只能被访问一次，被访问时打印。
如果一个节点能被访问两次，在第二次被访问时打印。

public void morrisLNR(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        // cur 左子树不为空
        if (cur.left != null) {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // 第一次访问 cur
                // ... do something
                mostRight.right = cur;
                cur = cur.left;
            } else {
                // 第二次访问 cur
                System.out.println(cur.val);
                // ... do something
                mostRight.right = null;
                cur = cur.right;
            }
        } else {
            System.out.println(cur.val);
            // ... do something
            cur = cur.right;
        }
    }
}

Morris - 后序

规则：
如果一个节点能被访问两次，在第二次被访问时自底向上打印该节点左子树的右边界。
当所有节点遍历完后，单独自底向上打印整棵树的右边界

public void morrisLRN(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        // cur 左子树不为空
        if (cur.left != null) {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // 第一次访问 cur
                // ... do something
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;
                
                // ... do something
                // 访问第二次时逆序打印左子树的右边界
                printRightEdge(cur.left);
                
                cur = cur.right;
            }
        } else {
            cur = cur.right;
        }
    }
    printRightEdge(root);
}

/**
 * 自底向上打印以root为根的右边界
 */
public void printRightEdge(TreeNode root) {
    TreeNode tail = reverseRightEdge(root);
    TreeNode cur = tail;
    while (cur != null) {
        System.out.println(cur.val);
        cur = cur.right;
    }
    reverseRightEdge(tail);
}

public TreeNode reverseRightEdge(TreeNode root) {
    TreeNode pre = null, next;
    while (root != null) {
        next = root.right;
        root.right = pre;
        pre = root;
        root = next;
    }
    return pre;
}