1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| using namespace std;
class BST { public: int value; BST *left = nullptr; BST *right = nullptr;
BST(int value) { this->value = value; } };
BST* helper(vector<int>& A, int& pos, int mi, int ma) { if(pos == A.size()) return nullptr; if(mi <= A[pos] and A[pos] < ma) { BST* bst = new BST(A[pos++]); bst->left = helper(A,pos,mi,bst->value); bst->right = helper(A,pos,bst->value,ma); return bst; } else return nullptr; }
BST *reconstructBst(vector<int> preOrderTraversalValues) { int pos = 0; return helper(preOrderTraversalValues, pos, INT_MIN, INT_MAX); }
|