leetcode --》 1008. 먼저 두 갈래 나무를 반복해서 구성한다

주어진 선순환 preorder 과 일치하는 두 갈래 검색 트리 (binary search tree) 의 루트 결점을 되돌려줍니다.
(돌이켜보면 두 갈래 검색 트리는 두 갈래 나무의 일종으로 그 각 노드는 다음과 같은 규칙을 만족시킨다. node.left의 모든 후손에 대한 값은 총<node.val이고 node.right의 모든 후손은 총>node.val이다.또한 노드의 값을 먼저 표시하고 node.left, 그 다음에 node.right 차례로 반복합니다.
 
예:

 ：[8,5,1,7,10,12]
 ：[8,5,10,1,7,null,12]

 
팁:

1 <= preorder.length <= 100

선서preorder의 값은 다르다.

본뜻은 앞 순서 + 중간 순서로 두 갈래 나무를 구하는 것이고, 중간 순서는sort 이후의 수조이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode bstFromPreorder(int[] pre) {
        int[] in = new int[pre.length];
        for (int i = 0; i < in.length; i++) {
            in[i] = pre[i];
        }
        Arrays.sort(in);
        //  + 
        return reConstructBinaryTree(pre, in);
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        //  ， 。
        int[] index = new int[pre.length];
        //  , index .
        for (int i = 0; i < pre.length; i++) {
            for (int j = 0; j < in.length; j++) {
                if (pre[i] == in[j]) {
                    index[j] = i;
                }
            }
        }
        TreeNode root = reConstructBinaryTree(in, index, 0, index.length - 1);
        return root;
    }

    private TreeNode reConstructBinaryTree(int[] in, int[] index, int head, int last) {
        if (head > last) {
            return null;
        }
        int minIndex = head;
        //  .
        for (int i = head + 1; i <= last; i++) {
            if (index[minIndex] > index[i]) {
                minIndex = i;
            }
        }
        //  。
        TreeNode root = new TreeNode(in[minIndex]);
        //  
        root.left = reConstructBinaryTree(in, index, head, minIndex - 1);
        root.right = reConstructBinaryTree(in, index, minIndex + 1, last);
        return root;
    }
}