【打卡】牛客网：BM34 判断是不是二叉搜索树

牛客网：BM34 判断是不是二叉搜索树"/>

【打卡】牛客网：BM34 判断是不是二叉搜索树

自己写的：

写了很久，调试了很久

一些细节如下：

递归的位置，需要放在return之前。因为调用的是主函数，所以要防止第一轮就return了。（很容易错）

调试很久的是return的时候需要加上"ans &&"。（很容易忽略这个点）

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root TreeNode类* @return bool布尔型*/int getMax(TreeNode* root){while(root->right != NULL)root = root->right;return root->val;}bool isValidBST(TreeNode* root) {// write code hereif (root == NULL)return true;if (root->left == NULL && root->right == NULL) return true;// 递归需要放在前面，防止进行第一轮就returnbool ans = isValidBST(root->left) && isValidBST(root->right);if (root->left != NULL) {int leftMax =  getMax(root->left);if (root->right == NULL)if (leftMax < root->val)return ans && true;elsereturn ans && false;else {if (leftMax < root->val && root->right->val > root->val)return ans && true;elsereturn ans && false;}} else {if(root->right->val > root->val)return ans && true;elsereturn ans && false;}// return ans;}
};

模板的：

非常nice。思路打开。

中序遍历的重要性：中序遍历和二叉搜索树是紧密关联的。

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root TreeNode类* @return bool布尔型*/long pre = INT_MIN;bool isValidBST(TreeNode* root) {// write code hereif (root == NULL)return true;if (!isValidBST(root->left))return false;if (pre >= root->val)return false;pre = root->val;if (!isValidBST(root->right))return false;return true;}
};