package wsj;
/**
 * 当前类所有函数 
 * ------------- 
 * [递归方式][前序]遍历二叉树：preOrderRecur() 
 * [递归方式][中序]遍历二叉树：inOrderRecur()
 * [递归方式][后序]遍历二叉树：posOrderRecur()
 * [非递归方式][前序]遍历二叉树：preOrderUnRecur()
 * [非递归方式][中序]遍历二叉树：inOrderUnRecur()
 * [非递归方式][后序]遍历二叉树：posOrderUnRecur()
 * [按层]遍历二叉树：printByLevel()
 * 由[前序遍历序列]和[中序遍历序列]重建二叉树：buildTreeByPreAndIn()
 * 由[后序遍历序列]和[中序遍历序列]重建二叉树：buildTreeByPosAndIn()
 */

import java.util.LinkedList;
import java.util.Stack;

//定义二叉树节点
class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        this.value = x;
    }
}

public class MyTree {
    // [递归方式][前序]遍历二叉树
    public static void preOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + "-");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    // [递归方式][中序]遍历二叉树
    public static void inOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left);
        System.out.print(root.value + "-");
        inOrderRecur(root.right);
    }

    // [递归方式][后序]遍历二叉树
    public static void posOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        posOrderRecur(root.left);
        posOrderRecur(root.right);
        System.out.print(root.value + "-");
    }

    // [非递归方式][前序]遍历二叉树
    public static void preOrderUnRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.print(cur.value + "-");
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    // [非递归方式][中序]遍历二叉树
    public static void inOrderUnRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            System.out.print(node.value + "-");
            cur = node.right;
        }
    }

    // [非递归方式][后序]遍历二叉树
    public static void posOrderUnRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode cur = root;
        stack1.push(cur);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value + "-");
        }
    }
    // [按层]遍历二叉树
    public static void printByLevel(TreeNode root){
        if (root==null) {
            return;
        }
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            TreeNode node=queue.pollFirst();
            System.out.print(node.value+"-");
            if (node.left!=null) {
                queue.addLast(node.left);
            }
            if (node.right!=null) {
                queue.addLast(node.right);
            }
        }
    }
    // 由[前序遍历序列]和[中序遍历序列]重建二叉树
    public static TreeNode buildTreeByPreAndIn(int[] pre, int[] in) {
        return buildProcess1(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    private static TreeNode buildProcess1(int[] pre, int preStart, int preEnd,
            int[] in, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int i = inStart;
        while (in[i] != pre[preStart]) {
            i++;
        }
        root.left = buildProcess1(pre, preStart + 1, preStart + i - inStart,
                in, inStart, i - 1);
        root.right = buildProcess1(pre, preStart + i - inStart + 1, preEnd, in,
                i + 1, inEnd);

        return root;
    }

    // 由[后序遍历序列]和[中序遍历序列]重建二叉树
    public static TreeNode buildTreeByPosAndIn(int[] pos, int[] in) {
        return buildProcess2(pos, 0, pos.length - 1, in, 0, in.length - 1);
    }

    private static TreeNode buildProcess2(int[] pos, int posStart, int posEnd,
            int[] in, int inStart, int inEnd) {
        if (posStart > posEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(pos[posEnd]);
        int i = inStart;
        while (in[i] != pos[posEnd]) {
            i++;
        }
        root.left = buildProcess2(pos, posStart, posStart + i - inStart - 1,
                in, inStart, i - 1);
        root.right = buildProcess2(pos, posStart + i - inStart, posEnd - 1, in,
                i + 1, inEnd);

        return root;
    }

    public static void main(String[] args) {
        int[] pre = { 1, 2, 4, 7, 3, 5, 6, 8 };
        int[] in = { 4, 7, 2, 1, 5, 3, 8, 6 };
        int[] pos = { 7, 4, 2, 5, 8, 6, 3, 1, };
        // TreeNode root = buildTreeByPreAndIn(pre, in);
        TreeNode root = buildTreeByPosAndIn(pos, in);

        preOrderRecur(root);
        System.out.println();
        preOrderUnRecur(root);
        System.out.println();

        inOrderRecur(root);
        System.out.println();
        inOrderUnRecur(root);
        System.out.println();

        posOrderRecur(root);
        System.out.println();
        posOrderUnRecur(root);
        System.out.println();
        
        printByLevel(root);
    }
}