import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
public static void main(String args[]) {

   Node head = new Node(1);
   head.left = new Node(2);
   head.right = new Node(3);
   head.left.left = new Node(4);
   head.left.right = new Node(5);
   head.right.left = new Node(6);
   head.right.right = new Node(7);

   // recursive
   System.out.println("==========recursive==========");
   System.out.print("pre-order: ");
   preOrderRecur(head);
   System.out.println();
   System.out.print("in-order: ");
   inOrderRecur(head);
   System.out.println();
   System.out.print("pos-order: ");
   posOrderRecur(head);
   System.out.println();

   // unrecursive
//   System.out.println("==========unrecursive==========");
//   preOrderUnRecur(head);
//   inOrderUnRecur(head);
//   posOrderUnRecur1(head);
//   posOrderUnRecur2(head);
}

public static class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
    }
}

public static void preOrderRecur(Node head) {
    if(head == null) {
        return;
    }
    System.out.print(head.val + " ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

public static void inOrderRecur(Node head) {
    if(head == null) {
        return;
    }

    inOrderRecur(head.left);
    System.out.print(head.val + " ");
    inOrderRecur(head.right);
}

public static void posOrderRecur(Node head) {
    if(head == null) {
        return;
    }

    posOrderRecur(head.left);
    posOrderRecur(head.right);
    System.out.print(head.val + " ");
}

public static void preOrderUnRecur(Node head) {
    System.out.print("pre-order: ");
    if(head != null) {
        Stack<Node> stack = new Stack<Node>();
        stack.add(head);
        while(!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.print(cur.val + " ");
            if(cur.right != null) {
                stack.push(cur.right);
            }
            if(cur.left != null) {
                stack.push(cur.left);
            }

        }
    }
    System.out.println();
}

public static void posOrderUnRecur1(Node head) {
    System.out.print("pos-order: ");
    if(head != null) {
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.add(head);
        while(!s1.isEmpty()) {
            Node cur = s1.pop();
            s2.push(cur);
            if(cur.left != null) {
                s1.push(cur.left);
            }
            if(cur.right != null) {
                s1.push(cur.right);
            }
        }
        while(!s2.isEmpty()) {
            System.out.print(s2.pop().val + " ");
        }
    }

    System.out.println();

}

public static void inOrderUnRecur(Node head) {
    System.out.print("in-order: ");
    Stack<Node> stack = new Stack<Node>();
    Node cur = head;

    //cur来到一个节点，只要有左边界，全部压栈，然后依次弹出节点，如果弹出节点有右子树，cur来到右子树的根节点把左边界全部压栈，
    //如果弹出节点没有右子树就继续弹出节点
    //会发现该流程中只有把子树的左边界压栈，原理：整棵树能被左边界分解
    while(!stack.isEmpty() || cur != null) {

        //把以cur为根的子树的左边界进栈，直到cur == null了然后开始弹节点
        if(cur != null) { //刚开始把整棵树的左边界压栈 或者 弹出节点的右子树不为空，要把右子树的左边界压栈时进入if，把左边界全都压栈
            stack.push(cur);
            cur = cur.left;
        } else { //左边界全都压栈了 或者 弹出节点的右子树为空时，此时cur == null，进入else，继续弹出节点
            cur = stack.pop();
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }
    System.out.println();
}

public static void w(Node head) {
    if(head == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(head);
    while(!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.print(cur.val + " ");
        if(cur.left != null) {
            queue.offer(cur.left);
        }
        if(cur.right != null) {
            queue.offer(cur.right);
        }
    }
    System.out.println();
}

//返回二叉树的最大宽度
public static int maxWidth(Node head) {
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(head);
    HashMap<Node, Integer> levelMap = new HashMap<>(); //levelMap表记录每个节点所在层数
    levelMap.put(head, 1);
    int curLevel = 1; //当前所在层，即要统计宽度的那一层，或者叫当前待统计层
    int max = 1; //最大宽度
    int curLevelNodes = 0; //当前待统计层已经发现的节点数
    while(!queue.isEmpty()) {
        Node cur = queue.poll();
        //当前遍历到的节点所在的层数，根据curNodeLevel来判断现在是继续统计该层，还是该结算了，即当前待统计层是否统计完了
        int curNodeLevel = levelMap.get(cur); 
        //如果当前遍历到的节点所在的层数==当前待统计的层数
        if(curNodeLevel == curLevel) {
            curLevelNodes++;
        } else { //如果不等于，一定是当前遍历到的节点已经是当前待统计层的下一层了，即当前待统计层已经统计完宽度了，该结算了
            max = Math.max(max, curLevelNodes);
            curLevel++;
            curLevelNodes = 1;
        }
        if(cur.left != null) {
            //每个进入队列的节点在二叉树中的层数都需要记录到levelMap表中
            //这样之后弹出该节点时，才能知道该节点的层数
            levelMap.put(cur.left, curLevel + 1);
            queue.offer(cur.left);
        }
        if(cur.right != null) {
            levelMap.put(cur.right, curLevel + 1);
            queue.offer(cur.right);
        }

    }

    return max;
}

}