題目
https://leetcode-cn.com/problems/validate-binary-search-tree/
思路
- 中序周遊,結果是順序的,用一個pre記錄前面節點的值,是以當周遊的節點的值小于pre,就是二叉搜尋樹了。
- 遞歸,棧+疊代實作中序周遊
- 不要在leetcode使用全局變量!不要在leetcode使用全局變量!不要在leetcode使用全局變量!😭
AC代碼
//疊代
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode *>s;
long long pre = LLONG_MIN; //卡INT_MIN。。
while (!s.empty() || root != NULL){
while(root){ //将所有的left節點壓入棧中
s.push(root);
root = root->left;
}
root = s.top(); //重點
if(root->val <= pre){
return false;
}
s.pop();
pre = root->val;
root = root->right;
}
return true;
}
};
//遞歸
class Solution {
public:
void f(TreeNode * root, long long &pre,bool &res){
if(root != NULL){
f(root->left, pre,res);
if(root->val <= pre) res = false;
pre = root->val;
f(root->right,pre,res);
}
}
bool isValidBST(TreeNode* root) {
if(root == NULL) return true;
long long pre = LLONG_MIN;
bool res = true;
f(root,pre,res);
return res;
}
};