using ll = long long; class Solution { protected: bool isBST(TreeNode* root, ll leftMin, ll rightMax){ if(!root) return true; if(root->val <= leftMin || root->val >= rightMax){ return false; } return isBST(root->left, leftMin, root->val) && isBST(root->right, root->val, rightMax); } public: bool isValidBST(TreeNode* root) { if(!root) return true; return isBST(root, LONG_MIN, LONG_MAX); } };
验证前序遍历序列是否满足二叉搜索树要求。
由于前序遍历的顺序为: root →left → right;
故遍历左子树的时候是递减的,可以用单调队列来进行维护。
对序列元素进行遍历,
如果当前元素小于最新出栈的元素,则必定不是二叉搜索树。
如果栈不空,而且当前元素val大于栈顶元素,说明开始进入右子树,那么弹出栈顶元素,更新到【最新栈顶元素pre】,直到该元素小于栈顶元素。
当前元素入栈
能遍历完所有元素,则为二叉搜索树。
class Solution { public: bool verifyPreorder(vector<int>& preorder) { int pre = INT_MIN; stack<int> monoStack; for(int i = 0; i < preorder.size(); i++){ int curVal = preorder[i]; if(curVal < pre){ return false; } while(!monoStack.empty() && monoStack.top() < curVal){ pre = monoStack.top(); monoStack.pop(); } monoStack.push(curVal); } return true; } }; //5 2 1 3 6