面试题7：重建二叉树

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

分析：

在二叉树的谦虚遍历序列中，第一个数字总是树的根节点的值。但在中序遍历序列中，根节点的值在序列的中间，左子树的结点的值位于根节点的值的左边，右子树的结点的值位于根节点的值的右边。因此，我们需要扫描中序遍历序列找到根节点，将中序遍历划分为两部分，根节点左侧的部分是根节点的左子树，根节点右侧的部分是根节点的右子树。其中的左子树和右子树又可以按照这种方式继续找根节点。

由此可以想到用递归的方式解决问题，

解法：

package com.wsy;

import java.util.Arrays;

class Tree {
    private int value;
    private Tree left;
    private Tree right;

    public Tree() {
    }

    public Tree(int value, Tree left, Tree right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Tree getLeft() {
        return left;
    }

    public void setLeft(Tree left) {
        this.left = left;
    }

    public Tree getRight() {
        return right;
    }

    public void setRight(Tree right) {
        this.right = right;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] preOrder = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
        int[] inOrder = new int[]{4, 7, 2, 1, 5, 3, 8, 6};
        Tree root = buildTree(preOrder, inOrder);
    }

    public static Tree buildTree(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null || preOrder.length <= 0 || inOrder.length <= 0) {
            return null;
        }
        Tree tree = new Tree(preOrder[0], null, null);
        int index = searchIndex(0, inOrder.length, inOrder, tree.getValue());
        tree.setLeft(buildTree(Arrays.copyOfRange(preOrder, 1, index + 1), Arrays.copyOfRange(inOrder, 0, index)));
        tree.setRight(buildTree(Arrays.copyOfRange(preOrder, index + 1, preOrder.length), Arrays.copyOfRange(inOrder, index + 1, inOrder.length)));
        return tree;
    }

    public static int searchIndex(int start, int end, int[] orders, int data) {
        for (int i = start; i < end; i++) {
            if (orders[i] == data) {
                return i;
            }
        }
        return -1;
    }
}