【剑指offer】重建二叉树 --Java实现

public class reConstructBinaryTreeTest {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 根据中序遍历和前序遍历重建二叉树
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        // 结点个数需要相同并且不能少于一个
        if (pre.length != in.length || pre.length < 1) {
            return null;
        }
        // 判断结点数是否为1，为1那就是根节点
        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }
        // 根据前序遍历所得的根节点去中序遍历中找其位置
        int root = pre[0];
        // 存储根节点在中序遍历中的索引
        int index = -1;
        for (int i = 0; i < in.length; i++) {
            if (root == in[i]) {
                index = i;
                break;
            }
        }
        // 如果没找到，代表测试用例有问题
        if (index == -1) {
            throw new RuntimeException("测试用例有问题");
        }
        TreeNode rootNode = new TreeNode(root);

        // 得到左子树的前序和中序遍历数组
        int[] leftChildIn = new int[index];
        System.arraycopy(in, 0, leftChildIn, 0, index);
        int[] leftChildPre = new int[index];
        System.arraycopy(pre, 1, leftChildPre, 0, index);

        // 递归得到左子树结构
        rootNode.left = reConstructBinaryTree(leftChildPre, leftChildIn);

        // 得到右子树的前序和中序遍历数组
        int rightChildCount = in.length - index - 1;
        int[] rightChildIn = new int[rightChildCount];
        System.arraycopy(in,index + 1,rightChildIn,0,rightChildCount);
        int[] rightChildPre = new int[rightChildCount];
        System.arraycopy(pre, index + 1, rightChildPre, 0, rightChildCount);

        // 递归得到右子树结构
        rootNode.right = reConstructBinaryTree(rightChildPre, rightChildIn);

        return rootNode;
    }

    @Test
    public void testreConstruct() {
        int[] prev = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode root = reConstructBinaryTree(prev,in);
        prevPrintTreeNode(root);
        System.out.println();
        inPrintTreeNode(root);
    }

    private void inPrintTreeNode(TreeNode root) {
        if (root == null) {
            return;
        }
        inPrintTreeNode(root.left);
        System.out.print(root.val + " ");
        inPrintTreeNode(root.right);
    }

    private void prevPrintTreeNode(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        prevPrintTreeNode(root.left);
        prevPrintTreeNode(root.right);
    }




}