Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

BST

Note:

1 <= preorder.length <= 100
The values of preorder are distinct.

解题思路

题目给出了先序遍历的结果，根据二叉搜索树的性质，我们知道左子树的节点都是小于根节点的，右子树的节点都是大于根节点的。所以做法如下：

1. 根据第一个元素构造根节点
2. 将除第一个元素外的其他元素按照大于或者小于根节点拆分为两个数组。
3. 用小于根节点的数组构造左子树。
4. 用大于根节点的数组构造右子树。

实现代码

// Runtime: 1 ms, faster than 82.36% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.
// Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.
/**
 * 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[] preorder) {
        if (preorder.length == 0) {
            return null;
        } else if (preorder.length == 1) {
            return new TreeNode(preorder[0]);
        } else {
            TreeNode root = new TreeNode(preorder[0]);
            int index = split(preorder);
            if (index > 1) {
                root.left = bstFromPreorder(Arrays.copyOfRange(preorder, 1, index));
            } 
            if (index < preorder.length) {
                root.right = bstFromPreorder(Arrays.copyOfRange(preorder, index, preorder.length));
            }
            return root;
        }
    }

    private int split(int[] preorder) {
        for (int i = 1; i < preorder.length; i++) {
            if (preorder[i] > preorder[0]) {
                return i;
            }
        }
        return preorder.length;
    }
}