java实现根据前序遍历和中序遍历重建二叉树

前序遍历：{1,2,4,7,3,5,6,8}

中序遍历：{4,7,2,1,5,3,8,6}

根据前序遍历第一个元素“1”，可以将中序遍历分成左右子树，左子树{4,7,2}，右子树{5,3,8,6}。

接着，根据前序遍历第二个元素“2”，将“1”的左子树{4,7,2}分为左子树{4,7}，右子树{}。

再根据前序遍历第三个元素“4”，将“2”的左子树{4,7}分为左子树{}，右子树{7}。

前序遍历第三个元素“7”，将“4”的右子树{7}分为左子树{}，右子树{}。

以此类推，通过递归的方式可以很容易重建二叉树。

public class BinaryTree {
    /**
     * 根据中序遍历和前序遍历重建二叉树
     * @param inOrderArray 中序遍历数组
     * @param start 中序遍历起点下标
     * @param end 中序遍历终点下标
     * @param list 前序遍历链表
     * @return 返回二叉树
     */
    public static TreeNode createTree(int[] inOrderArray, int start, int end, LinkedList<Integer> list){
        //返回前序遍历链表的首结点，即为子树的根结点
        int item = list.removeFirst();
        TreeNode node = new TreeNode(item);
        //获取根结点在中序遍历数组中的位置下标
        int index = getRootIndex(inOrderArray,item,start,end);
        //递归构建左子树
        //start == index表示该结点没有左子树
        if (start == index){
            node.setLeft(null);
        }else {
            node.setLeft(createTree(inOrderArray,start,index-1,list));
        }

        //递归构建右子树
        //index == end表示该结点没有右子树
        if (index == end){
            node.setRight(null);
        }else {
            node.setRight(createTree(inOrderArray,index+1,end,list));
        }
        return node;
    }

    /**
     * 获取根节点值在中序遍历中的下标
     * @param inOrderArray 中序遍历数组
     * @param item 根结点的值
     * @param start 中序遍历起点下标
     * @param end 中序遍历终点下标
     * @return 返回根节点值在中序遍历中的下标
     */
    private static int getRootIndex(int[] inOrderArray,int item,int start,int end){
        for (int i = start;i<=end;i++){
            if (inOrderArray[i] == item){
                return i;
            }
        }
        return -1;
    }

    /**
     * 前序遍历输入二叉树
     */
    private static void preOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        System.out.print(node.getItem() + " ");
        preOrderTraveral(node.getLeft());
        preOrderTraveral(node.getRight());
    }

    private static void inOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        inOrderTraveral(node.getLeft());
        System.out.print(node.getItem() + " ");
        inOrderTraveral(node.getRight());
    }

    public static void main(String[] args) {
        int[] a = {4,7,2,1,5,3,8,6};
        LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer[]{1,2,4,7,3,5,6,8}));
        TreeNode node = createTree(a,0,a.length-1,list);
        preOrderTraveral(node);
        System.out.println();
        inOrderTraveral(node);
        System.out.println();
        
        int[] c = {2};
        LinkedList<Integer> list3= new LinkedList<>(Arrays.asList(new Integer[]{2}));
        TreeNode node3 = createTree(c,0,c.length-1,list3);
        preOrderTraveral(node3);
        System.out.println();

        int[] d = {5,4,3,2};
        LinkedList<Integer> list4 = new LinkedList<>(Arrays.asList(new Integer[]{2,3,4,5}));
        TreeNode node4 = createTree(d,0,d.length-1,list4);
        preOrderTraveral(node4);
    }
    /*
     * 1 2 4 7 3 5 6 8
     * 4 7 2 1 5 3 8 6
     * 
     * 2
     * 
     * 2 3 4 5
     */
}

public class TreeNode {
    private  int item;
    private TreeNode left;
    private TreeNode right;
//getter和setter
}