【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

• 其實就是做實作二元搜索樹的插入功能，然後按照順序放進去而已，好像也沒啥好講的。
  • 如果你對樹或是二元搜索樹不熟，可以參考我的另一份攻略或是我的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++