# 【LeetCode】 1008. Construct Binary Search Tree from Preorder Traversal

## Description
> 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.)

> Note:
> * 1 <= preorder.length <= 100
> * The values of preorder are distinct.

> 給予一個前序遍歷，回傳對應的二元搜索樹的根節點。
> （所謂的二元搜索樹是一種二元樹，其每一個節點的左子樹之值都小於自己，右子樹之值都大於自己。而所謂的前序遍歷是指從一棵樹的任一節點開始，先顯示它自己的值，再跑左子樹，最後跑右子樹。）

> 注意:
> * 1 <= preorder.length <= 100
> * 所有preorder的值都不同。

## Example:

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


## Solution

* 其實就是做實作二元搜索樹的插入功能，然後按照順序放進去而已，好像也沒啥好講的。
* 如果你對樹或是二元搜索樹不熟，可以參考我的[另一份攻略](https://hackmd.io/@Zero871015/DSNote)或是我的[BST實作](https://github.com/Zero871015/BST)。

### Code

/**
 * 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:
    void insert(TreeNode* node, int num)
    {
        if(node->val > num)
        {
            if(node->left == NULL)
                node->left = new TreeNode(num);
            else
                insert(node->left, num);
        }
        else if(node->val < num)
        {
            if(node->right == NULL)
                node->right = new TreeNode(num);
            else
                insert(node->right, num);
        }
    }
    
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode(preorder[0]);
        for(int i = 1; i < preorder.size(); i++)
            insert(root, preorder[i]);
        return root;
    }
};

###### tags: `LeetCode` `C++`