验证二叉搜索树-力扣

第一次做这道题时，想的解法是递归去判断比较左节点小于中间节点，右节点大于中间节点，而这恰恰进入了陷阱，这道题不仅仅是判断子树是否左节点小于中间节点，右节点大于中间节点；要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。附上错误代码：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        bool isTrue = 0;
        if(root->left == nullptr && root->right == nullptr){
            isTrue = true;
        }else if(root->left == nullptr && root->val < root->right->val){
            isTrue = true;
        }else if(root->right == nullptr && root->val > root->left->val){
            isTrue = true;
        }else if(root->left != nullptr && root->right != nullptr && root->val < root->right->val && root->val > root->left->val){
            isTrue = true;
        }else{
            isTrue = false;
        }
        return isTrue && isValidBST(root->left) && isValidBST(root->right);
    }
};

正确的递归应该是使用中序遍历的顺序，挨个比较两两大小，是否满足二叉搜索树的性质，这里利用一个全局变量pre来记录当前节点的前一个节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pre = NULL;
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root;

        bool right = isValidBST(root->right);
        return left && right;
    }
};

也可以使用中序遍历得到一个数组，然后遍历这个数组，如果这个数组是递增的，则这个树二叉搜索树。

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};