題目鏈接：98. 驗證二叉搜索樹 - 力扣（LeetCode）
首先列舉一個錯誤代碼
class Solution {
public:bool isValidBST(TreeNode* root) {if(root==nullptr) return true;if(root->right){if(root->right->val<=root->val) return false;} if(root->left){if(root->left->val>=root->val) return false;}return isValidBST(root->left)&&isValidBST(root->right);}
};
反例：
這段代碼僅關注于局部，僅考慮根節點的左右結點是否滿足二叉搜索樹的條件，沒有考慮根結點的整個左右子樹是否滿足二叉搜索樹的條件。
修正： 抓住二叉搜索樹的一個性質：二叉搜索樹的中序遍歷是升序的。用遞歸的方法中序遍歷二叉搜索樹，用pre記錄前一個結點，并在中間和當前的根節點比較。
class Solution {
public:TreeNode* pre=nullptr;bool isValidBST(TreeNode* root) {//遞歸終止的條件if(root==nullptr) return true;//遍歷左子樹if(!isValidBST(root->left)) return false;//判斷是否是二叉搜索樹if(pre!=nullptr&&pre->val>=root->val) return false;pre=root;//遍歷右子樹return isValidBST(root->right);}
};
- 時間復雜度：O(n)
- 空間復雜度：O(n)
關于pre指針的一些思考： 如果是二叉搜索樹，按照中序遍歷，pre指針的值會依次增大，滿足代碼中的判斷條件；如果不是則相反。
