题解 | #遍历二叉树的神级方法#

import java.io.;
import java.util.;

public class Main{
static class Node{
public int value;
public Node left;
public Node right;

    public Node(int data){
        this.value=data;
    }
}
/*Morris遍历
时间复杂度O(N),空间复杂度O(1)
假设当前节点为cur，初始cur就是整棵树的头节点，根据以下标准让cur移动：
1、如果cur为null，则过程停止，否则继续下面的过程
2、如果cur没有左子树，则让cur向右移动，cur=cur.right
3、如果cur有左子树，则找到cur左子树最右的节点，记为mostRight
    1)如果mostRight的right指针指向null，令mostRight.right=cur，也就是让mostRight的right指针指向当前节点
        然后cur向左移动，cur=cur.left
    2)如果mostRight的right指针指向cur，令mostRight.right=null,也就是让mostRight的right指针指向null
        然后cur向右移动，cur=cur.right
* */
public static void morris(Node head){
    //1、
    if(head==null){
        return;
    }
    Node cur=head;
    Node mostRight=null;
    while (cur!=null){
        mostRight=cur.left;
        if(mostRight!=null){    //cur有左子树
            //找到cur左子树的最右节点
            while (mostRight.right!=null&&mostRight.right!=cur){
                mostRight=mostRight.right;
            }
            //从上面while出来，mostRight就是cur左子树的最右节点
            if(mostRight.right==null){
                mostRight.right=cur;
                cur=cur.left;
                continue;//回到最外层while，继续判断cur情况
            }else {     //如果mostRight.right指向cur
                mostRight.right=null;
            }

        }
        //cur如果没有左子树，cur向右移动
        //或者cur左子树的最右节点的right指向cur,cur向右移动
        cur=cur.right;
    }

}


/*先序遍历      根 左 右
1、对于cur只能到达一次的节点(无左子树的节点)，cur到达时直接打印
2、对于cur到达两次的节点(有左子树的节点)，cur第一次到达时打印，第二次到达时不打印
* */
public static void morrisPre(Node head){
    if(head==null){
        return;
    }

    Node cur=head;
    Node mostRight=null;
    while (cur!=null){
        mostRight=cur.left;
        //cur有左子树
        if(mostRight!=null){
            //找出左子树的最右节点
            while (mostRight.right!=null&&mostRight.right!=cur){
                mostRight=mostRight.right;
            }
            //mostRight.right是否指向null
            if(mostRight.right==null){
                mostRight.right=cur;
                System.out.print(cur.value+" ");
                cur=cur.left;
                continue;
            }else {
                mostRight.right=null;
            }
        }else {
            System.out.print(cur.value+" ");
        }
        cur=cur.right;
    }

}


/*中序遍历      左 根 右
1、对于cur只能到达一次的节点(无左子树的节点)，cur到达时直接打印
2、对于cur到达两次的节点(有左子树的节点)，cur第一次到达时不打印，第二次到达时打印
* */
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;
            }
            //左子树最右节点的right指针是否为null
            if(mostRight.right==null){
                mostRight.right=cur;
                cur=cur.left;
                continue;
            }else {
                mostRight.right=null;
            }
        }
        System.out.print(cur.value+" ");
        cur=cur.right;

    }
}


/*后序遍历      左 右 根
1、对于cur只能到达一次的节点(无左子树的节点)，直接跳过
2、对于cur到达两次的节点(有左子树的节点)X，cur第一次到达X时，没有打印行为；
    第二次到达X时，逆序打印X左子树的右边界
3、cur遍历完成后，逆序打印整棵树的右边界
* */
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;
            }
            //最右节点的right指针是否指向null
            if(mostRight.right==null){  //第一次到达
                mostRight.right=cur;
                cur=cur.left;
                continue;
            }else {                 //第二次到达
                mostRight.right=null;
                printEdge(cur.left);    //逆序打印左子树的右边界
            }

        }
        cur=cur.right;

    }
    //3、逆序打印整棵树的右边界
    printEdge(head);

}


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;
}

/*
in: 3 1
    1 2 3
    2 0 0
    3 0 0
out:1 2 3
    2 1 3
    2 3 1
* */
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String[] input = in.nextLine().split(" ");
    int n = Integer.parseInt(input[0]);
    Node root = new Node(Integer.parseInt(input[1]));
    HashSet<Node> set = new HashSet<Node>();
    set.add(root);

    for (int i = 0; i < n; i++) {
        //build the binary tree
        String[] nodes = in.nextLine().split(" ");
        int fatherValue = Integer.parseInt(nodes[0]);
        int leftValue = Integer.parseInt(nodes[1]);
        int rightValue = Integer.parseInt(nodes[2]);
        //遍历添加
        for (Node e : set) {
            //1、比较根节点
            if (e.value == fatherValue) {
                //2、建立左右节点
                e.left = leftValue == 0 ? null : new Node(leftValue);
                e.right = rightValue == 0 ? null : new Node(rightValue);
                //3、将左右节点添加进HashSet
                if (leftValue != 0) {
                    set.add(e.left);
                }
                if (rightValue != 0) {
                    set.add(e.right);
                }
                //4、此行遍历完，该舍弃
                set.remove(e);
                break;
            }
        }
    }

    morrisPre(root);
    System.out.println();
    morrisIn(root);
    System.out.println();
    morrisPos(root);
    System.out.println();
}

}