Morris traversal

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

本质上是inorder的traversal。把当前结点的左儿子的最右的叶子结点（也就是在inorder顺序上，当前结点的前一个结点）的右结点指向当前。当第2次到达这个结点的时候，可以重新给断开
时间跟空间都是 O(1)

void morris(TreeNode root) {

    TreeNode cur = root, pre = null;
    while (cur != null) {
        if (cur.left != null) {
            pre = cur.left;
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }

            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            }else {
                System.out.println(cur.val);
                cur = cur.right;
                pre.right = null;
            }
        }else {
            System.out.println(cur.val);
            cur = cur.right;
        }
    }
}

Morris traversal iterator
public class OA {

    public static void main(String[] ss) {
        Node n50 = new Node(50);
        Node n40 = new Node(40);
        Node n30 = new Node(30);
        Node n1 = new Node(1);
        Node n35 = new Node(35);
        Node n45 = new Node(45);
        Node n60 = new Node(60);
        Node n55 = new Node(55);

        n50.left = n40;
        n50.right = n60;
        n60.left = n55;
        n40.left = n30;
        n40.right = n45;
        n30.left = n1;
        n30.right = n35;
        
        MoItr itr = new MoItr(n50);

        for (int i = 0; i < 8; i++) {
            System.out.println(itr.next());
        }
    }

    static class MoItr{

        private Node root;
        public MoItr(Node root) {
            this.root = root;
        }

        public int next() {

            while (root != null) {
                if (root.left != null) {

                    Node pre = root.left;
                    while (pre.right != null && root != pre.right) {
                        pre = pre.right;
                    }

                    if (pre.right == null) {
                        pre.right = root;
                        root = root.left;
                    }else {
                        int rt = root.val;
                        pre.right = null;
                        root = root.right;
                        return rt;
                    }

                }else {
                    int rt = root.val;
                    root = root.right;
                    return rt;
                }
            }



            return -1;
        }

    }

}