题解 | #判断是不是二叉搜索树#
判断是不是二叉搜索树
https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: long pre = LONG_MIN;//前驱 //中序遍历 // bool isValidBST(TreeNode* root) { // if(root==nullptr) return true; // bool left=isValidBST(root->left); // //判断当前值 // bool cur=false; // if(root->val>pre) // cur =true; // //修改pre // pre=root->val; // //判断右子树 // bool right=isValidBST(root->right); // return left&&cur&&right; // } //方法二 : bool isValidBST(TreeNode* root) { if (root == nullptr) return true; bool left = isValidBST(root->left); if(left==false) return false;// 剪枝 //判断当前值 bool cur = false; if (root->val > pre) cur = true; if(cur==false) return false;// 剪枝 //修改pre pre = root->val; //判断右子树 bool right = isValidBST(root->right); if(right==false) return false;// 剪枝 return left && cur && right; } };
通过不断验证二叉树的中序遍历是有序的这个性质,利用全局变量来不断比较。使用剪枝的方式可以很大程度上加跨搜索过程