Construct Binary Search Tree from Preorder Traversal

从preorder建bst.

这个题要先通过排序找到inorder, 因为inorder中的root在中间, 所以知道左右就是leaf, 通过记录leaf的value, 知道位置, 然后就可以确定bst了.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        int[] inorder = new int[preorder.length];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < preorder.length; i++) {
            inorder[i] = preorder[i]; 
        }
        Arrays.sort(inorder);
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return toTree(map, preorder, inorder, 0, inorder.length - 1);
    }
    int preIndex = 0;
    private TreeNode toTree(Map<Integer, Integer> map, int[] pre, int[] in, int start, int end) {
        if(start > end)
            return null; 
        TreeNode root = new TreeNode(pre[preIndex]);
        int inIndex = map.get(pre[preIndex]);
        preIndex++;
        root.left = toTree(map, pre, in, start, inIndex - 1);
        root.right = toTree(map, pre, in, inIndex + 1, end);
        return root;
    }
}