判断二叉搜索树

      判断是否为二叉搜索树有两种方法：

     1.递归     

//val表示值 //left是左子树 //right是右子树 //lower 下界 比最小值还小 //upper 上界 比最大值还大 class Solution { public:bool helper(TreeNode* root, long long lower, long long upper) {if (root == nullptr) return true;if (root -> val <= lower || root -> val >= upper) //=也不行return false;return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);}bool isValidBST(TreeNode* root) {return helper(root, LONG_MIN, LONG_MAX);}};

 

     2.中序遍历

由二叉搜索树的性质，中序遍历序列是递增的。

//中序遍历是升序 class Solution { public:bool isValidBST(TreeNode* root) {stack<TreeNode*> stack; //栈存放树的节点long long inorder = (long long)INT_MIN - 1;while (!stack.empty() || root != nullptr) {while (root != nullptr) {//入栈stack.push(root);//左子树全部入栈root = root -> left;}root = stack.top();stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树if (root -> val <= inorder) return false;inorder = root -> val;root = root -> right;}return true;} };

从最左的孩子开始，每次top和pop遍历元素。

两个算法时间复杂度和空间复杂度都是O(n)

参考地址：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

总结

以上是生活随笔为你收集整理的判断二叉搜索树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。