Morris遍历二叉树（非递归，不用栈，O(1)空间）

╰+攻爆jí腚メ 2022-05-15 10:24 98阅读 0赞

# 一、[概述][Link 1] #

实现二叉树的前中后序遍历，达到要求：

1.  O(1)空间复杂度，即只能使用常数空间；
2.  二叉树的形状不能被破坏（中间过程允许改变其形状）。

# 二、代码详解 #

/** * Morris遍历 * @author superman * */
    public class MorrisTraversal {
    
    
    
        public static void process(Node head) {
            if(head == null) {
                return;
            }
    
            // 1
            //System.out.println(head.value);
    
    
            process(head.left);
    
            // 2
            //System.out.println(head.value);
    
    
            process(head.right);
    
            // 3
            //System.out.println(head.value);
        }
    
    
        public static class Node {
            public int value;
            Node left;
            Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static void morrisIn(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;
                        cur1 = cur1.left;
                        continue;
                    } else {
                        cur2.right = null;
                    }
                }
                System.out.print(cur1.value + " ");
                cur1 = cur1.right;
            }
            System.out.println();
        }
    
        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();
        }
    
        public static void morrisPos(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;
                        cur1 = cur1.left;
                        continue;
                    } else {
                        cur2.right = null;
                        printEdge(cur1.left);
                    }
                }
                cur1 = cur1.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;
        }
    
        // for test -- print tree
        public static void printTree(Node head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }
    
        public static void printInOrder(Node head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.right, height + 1, "v", len);
            String val = to + head.value + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.left, height + 1, "^", len);
        }
    
        public static String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }
    
        public static void main(String[] args) {
            Node head = new Node(4);
            head.left = new Node(2);
            head.right = new Node(6);
            head.left.left = new Node(1);
            head.left.right = new Node(3);
            head.right.left = new Node(5);
            head.right.right = new Node(7);
            printTree(head);
            morrisIn(head);
            morrisPre(head);
            morrisPos(head);
            printTree(head);
    
        }
    
    }

[Link 1]: https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html