剑指offer 面试题6—重建二叉树

题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。

分析：

前序遍历的第一个节点时根，在中序中找到这个根节点，然后左边就是左子树，右边就是右子树，这样就可以递归。

用数组来记录，然后每次还重新弄数组，把左子树复制过来，右子树复制过来，递归。

public TreeNode constructionOfTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }

        if (pre.length == 1 && in.length == 1) {
            return new TreeNode(pre[0]);
        }

        int len = pre.length;
        int root = pre[0];
        TreeNode tree = new TreeNode(root);

        int del = -1;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == root) {
                del = i;
                break;
            }
        }

        int right_length = in.length - del - 1;
        int[] left_pre = new int[del];
        int[] left_in = new int[del];
        int[] right_pre = new int[right_length];
        int[] right_in = new int[right_length];

        for (int i = 1; i < del + 1; i++) {
            left_pre[i - 1] = pre[i];
            left_in[i - 1] = in[i - 1];
        }

        for (int i = del + 1; i < pre.length; i++) {
            right_pre[i - del - 1] = pre[i];
            right_in[i - del - 1] = in[i];
        }

        tree.left = constructionOfTree(left_pre, left_in);
        tree.right = constructionOfTree(right_pre, right_in);

        return tree;
    }

下面这种我觉得好些，用记录长度的方式，不用重复建立数组。

/**
     *
     * @param preOrder 前序遍历数组
     * @param inOrder 中序遍历数组
     * @param length 数组长度
     * @return 根结点
     */
    public static BinaryTreeNode Construct(int[] preOrder, int[] inOrder,int length){
        if (preOrder == null || inOrder == null || length <= 0) {
            return null;
        }
        try {
            return ConstructCore(preOrder, 0, preOrder.length - 1, inOrder, 0,inOrder.length - 1);
        } catch (InvalidPutException e) {
            e.printStackTrace();
            return null;
        }
    }  

    /**
     *
     * @param PreOrder
     *            前序遍历序列
     * @param startPreIndex
     *            前序序列开始位置
     * @param endPreIndex
     *            前序序列结束位置
     * @param InOrder
     *            中序遍历序列
     * @param startInIndex
     *            中序序列开始位置
     * @param endInIndex
     *            中序序列结束位置
     * @return 根结点
     * @throws InvalidPutException
     */
    public static BinaryTreeNode ConstructCore(int[] preOrder,int startPreIndex, int endPreIndex,
            int[] inOrder,int startInIndex, int endInIndex) throws InvalidPutException {  

        int rootValue = preOrder[startPreIndex];
        System.out.println("rootValue = " + rootValue);
        BinaryTreeNode root = new BinaryTreeNode(rootValue);  

        // 只有一个元素
        if (startPreIndex == endPreIndex) {
            if (startInIndex == endInIndex
                    && preOrder[startPreIndex] == inOrder[startInIndex]) {
                System.out.println("only one element");
                return root;
            } else {
                throw new InvalidPutException();
            }
        }  

        // 在中序遍历中找到根结点的索引
        int rootInIndex = startInIndex;  

        while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {
            ++rootInIndex;
        }  

        if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {
            throw new InvalidPutException();  

        }  

        int leftLength = rootInIndex - startInIndex;  

        int leftPreOrderEndIndex = startPreIndex + leftLength;  

        if (leftLength > 0) {
            // 构建左子树
            root.leftNode = ConstructCore(preOrder, startPreIndex + 1,
                    leftPreOrderEndIndex, inOrder, startInIndex,
                    rootInIndex - 1);
        }  

        if (leftLength < endPreIndex - startPreIndex) {
            // 右子树有元素,构建右子树
            root.rightNode = ConstructCore(preOrder, leftPreOrderEndIndex + 1,
                    endPreIndex, inOrder, rootInIndex + 1, endInIndex);
        }
        return root;
    }  

    static class InvalidPutException extends Exception {  

        private static final long serialVersionUID = 1L;  

    }  

    public static void printPreOrder(BinaryTreeNode root) {
        if (root == null) {
            return;
        } else {
            System.out.print(root.value + " ");
        }  

        if (root.leftNode != null) {
            printPreOrder(root.leftNode);
        }  

        if (root.rightNode != null) {
            printPreOrder(root.rightNode);
        }
    }  

    public static void main(String[] args) throws Exception{
        ConstructionOfTree test=new ConstructionOfTree();
        int[] preOrder={1,2,4,7,3,5,6,8};
        int[] inOrder={4,7,2,1,5,3,8,6};
        printPreOrder(test.Construct(preOrder, inOrder, preOrder.length));
    }  

BinaryTreeNode.java

public class BinaryTreeNode {
    public int value;
    public BinaryTreeNode leftNode;
    public BinaryTreeNode rightNode;

    public BinaryTreeNode() {

    }

    public BinaryTreeNode(int value) {
        this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }
}