LeetCode - 1008 解題紀錄

題目： LeetCode - 1008. Construct Binary Search Tree from Preorder Traversal

題目說明

給一個陣列，將陣列造成一個二元搜尋樹。

解題思路

• 想法：樹根的值一定是 preorder[0]，使用 pos 來記數，然後先建左邊，建到 preorder[pos] 大於樹根的值時再建右邊。
• 作法：使用遞迴即可。

參考解法

class Solution {
public:
    int pos = 0;
    TreeNode* bstFromPreorder(vector<int>& preorder, int max = INT_MAX) {
        if(pos == preorder.size() || preorder[pos] > max)   
            return nullptr;
        return new TreeNode(preorder[pos], bstFromPreorder(preorder, preorder[pos++]), bstFromPreorder(preorder, max));
    }
};