1008. Construct Binary Search Tree from Preorder Traversal

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

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]

Solution

根据BST的先序遍历结果还原BST。先序遍历第一个元素是root，要在剩余元素中找左右子树的分界点。BST的中序遍历是排好序的数组，利用此性质就得到了中序遍历结果，用前序和中序可以还原出任意二叉树。但这么做排序时间复杂度为O(NlgN)。实际上只需要先序遍历和BST左子树都比root小，右都比它大自然就得到了分割点。

/*
 * @lc app=leetcode id=1008 lang=cpp
 *
 * [1008] Construct Binary Search Tree from Preorder Traversal
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int cur = 0;
    TreeNode* bstFromPreorder(vector<int>& preorder, int bound = INT_MAX) {
        if (cur == preorder.size() || preorder[cur] >= bound) return nullptr;
        TreeNode *node = new TreeNode(preorder[cur++]);
        node->left = bstFromPreorder(preorder, node->val);
        node->right = bstFromPreorder(preorder, bound);
        return node;
    }
};
// @lc code=end