[검지 Offer] - 두 갈래 트리 재구성 [Java 버전]

제목은 어떤 두 갈래 나무의 앞 순서와 중간 순서를 입력한 결과를 설명합니다. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.

/**
 * Created by Joe on 2018/6/6
 */
/**
 * Created by Joe on 2018/6/6
 */
public class Main {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        //  1， 
        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }

        //  1， 
        if (pre.length > 1) {
            //  ， 
            int rootIndex = findIndex(pre[0], in);
            TreeNode node = new TreeNode(pre[0]);


            //  
            int leftLength = rootIndex;
            int[] preLeft = new int[leftLength];
            System.arraycopy(pre, 1, preLeft, 0, leftLength);
            int[] inLeft = new int[leftLength];
            System.arraycopy(in, 0, inLeft, 0, leftLength);
            //  
            node.left = reConstructBinaryTree(preLeft, inLeft);

            //  
            int rightLength = in.length - 1 - rootIndex;
            int[] preRight = new int[rightLength];
            System.arraycopy(pre, 1 + leftLength, preRight,0, rightLength);
            int[] inRight = new int[rightLength];
            System.arraycopy(in, rootIndex + 1, inRight, 0, rightLength);
            //  
            node.right = reConstructBinaryTree(preRight, inRight);

            return node;
        }
        return null;
    }

    public static void preTravle(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + ",");
            preTravle(node.left);
            preTravle(node.right);
        }
    }

    public int findIndex(int val, int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (val == arr[i]) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        TreeNode root = new Main().reConstructBinaryTree(
                new int[] {1,2,4,3,5,6},
                new int[] {4,2,1,5,3,6}
        );

        preTravle(root);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}