剑指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;
    }
}