? ? ? 判斷是否為二叉搜索樹有兩種方法：

? ? ?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.中序遍歷

由二叉搜索樹的性質(zhì)，中序遍歷序列是遞增的。

//中序遍歷是升序 class Solution { public:bool isValidBST(TreeNode* root) {stack<TreeNode*> stack; //棧存放樹的節(jié)點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();// 如果中序遍歷得到的節(jié)點的值小于等于前一個 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/

總結

以上是生活随笔為你收集整理的判断二叉搜索树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。