package utils;

import java.util.Arrays;

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

public class BinaryTree {
	// 先序遍歷  根-左-右
	private static void firstOrder(Node root) {
		if (root ==null)return;
		System.out.print(root.val);
		firstOrder(root.left);
		firstOrder(root.right);
	}
	
	// 中序遍歷  左-根-右
	private static void inOrder(Node root) {
		if (root ==null)return;
		inOrder(root.left);
		System.out.print(root.val);
		inOrder(root.right);
	}

	// 后序遍歷  左-右-根
	private static void lastOrder(Node root) {
		if (root ==null)return;
		lastOrder(root.left);
		lastOrder(root.right);
		System.out.print(root.val);
	}
	
	// 根據(jù)先序遍歷和后序遍歷重構二叉樹
    private static Node reConstructBinaryTree(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        int len = preOrder.length;
        Node node = new Node(preOrder[0]);
        for (int i=0; i<len; i++) {
            if (preOrder[0] == inOrder[i]) {
                node.left = reConstructBinaryTree(
                        Arrays.copyOfRange(preOrder, 1, i+1),
                        Arrays.copyOfRange(inOrder, 0, i)
                );
                node.right = reConstructBinaryTree(
                        Arrays.copyOfRange(preOrder, i+1, len),
                        Arrays.copyOfRange(inOrder, i+1, len)
                );
            }
        }
        return node;
    }
	
	// 根據(jù)中序遍歷和后續(xù)遍歷重構二叉樹
    private static Node reConstructBinaryTree2(int[] inOrder, int[] lastOrder) {
        if (lastOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        int len = lastOrder.length;
        Node node = new Node(lastOrder[len-1]);
        for (int i=0; i<len; i++) {
            if (lastOrder[len-1] == inOrder[i]) {
                node.left = reConstructBinaryTree2(
                        Arrays.copyOfRange(inOrder, 0, i),
                        Arrays.copyOfRange(lastOrder, 0, i)
                );
                node.right = reConstructBinaryTree2(
                        Arrays.copyOfRange(inOrder, i+1, inOrder.length),
                        Arrays.copyOfRange(lastOrder, i, lastOrder.length-1)
                );
            }
        }
        return node;
    }

    public static void main(String[] args) {
        int[] preOrder = {1,2,7,4,5,3,6,8};
        int[] inOrder = {7,2,5,4,1,6,3,8};
        int[] lastOrder = {7,5,4,2,6,8,3,1};
        Node root = reConstructBinaryTree(preOrder, inOrder);
        lastOrder(root);
        System.out.println();
        root = reConstructBinaryTree2(inOrder, lastOrder);
        firstOrder(root);
    }

}