public class Test1 {
    public static void main(String[] args) throws InterruptedException {
        String perOrderStr = "ABHFDECKG";//前序序列
        String inOrderStr = "HBDFAEKCG";//中序序列
        BiTree node = createBiTree(perOrderStr, inOrderStr);
        //輸出前序遍歷驗證正確性
        BiTree.preOrdertrasver(node);
    }
    static class BiTree {
        char data;
        BiTree left;
        BiTree right;
        public BiTree(char data) {
            this.data = data;
        }
        public static void preOrdertrasver(BiTree tree) {
            if (tree != null) {
                System.out.print(tree.data);
                preOrdertrasver(tree.left);
                preOrdertrasver(tree.right);
            }
        }
    }
    static BiTree createBiTree(String preOrderStr, String inOrderStr) {
        if (preOrderStr.length() == 0 || inOrderStr.length() == 0) {
            return null;
        }
        //樹的根節(jié)點
        char root = preOrderStr.charAt(0);
        //創(chuàng)建節(jié)點
        BiTree node = new BiTree(root);
        //左右子樹的根節(jié)點索引
        int index = inOrderStr.indexOf(root);
        //左子樹str
        String leftSubTreeStr = inOrderStr.substring(0, index);
        //右子樹str
        String rightSubTreeStr = inOrderStr.substring(index + 1);
        node.left = createBiTree(preOrderStr.substring(1, index + 1), leftSubTreeStr);
        node.right = createBiTree(preOrderStr.substring(index + 1), rightSubTreeStr);
        return node;
    }
}