题目描述

原题链接98. 验证二叉搜索树

解题思路

BST的特点是当前结点的值比左子树中的全部结点都大比右子树中全部结点都小。在代码实现中要注意不要对比的是某一结点和某一侧的全部值之间的关系不能只有结点与结点间的关系对比否则容易出现非法BST。

一、递归法

根据BST的特征

1中序遍历

根据BST的特点当对BST进行中序遍历时结点的值应呈单调递增的形式。

1辅助vector
根据单调性我们可以在遍历时用vector记录结点值然后再顺序遍历vector中的值当以单调形式递增时返回true否则返回false。

/**
 * 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:
    vector<int> path;
    // 按中序遍历左中右的顺序将root中元素存入path中
    void traversal(TreeNode* root) {
        if(!root)       return ;
        traversal(root->left);
        path.push_back(root->val);
        traversal(root->right);
    }
    bool isValidBST(TreeNode* root) {
        traversal(root);
        // 若为BST则path中元素应该单调递增
        for(int i = 0; i < path.size() - 1; i++) {
            if(path[i] >= path[i + 1])       return false;
        }
        return true;
    }
};

2记录上一个结点的值
设置maxValue记录上一个遍历元素的值若为BST则当前的值应大于上一个遍历的值。

/**
 * 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:
    // 因为测试数据中有INT_MIN和INT_MAX所以用long long
    long long maxValue = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(!root)       return true;
        bool left = isValidBST(root->left);
        // 中序遍历验证元素是否从小到大递增
        if(maxValue < root->val)    maxValue = root->val;
        else            return false;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

3双指针法
为防止测试数据有LONG_MIN因此采用记录前后元素双指针对比数据大小的方式。

/**
 * 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)       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;
    }
};

2先序遍历

BST要保证当前节点全部大于左子树中的结点全部小于右子树中的结点。

在向左子树遍历时只会遇到两种情况
1向左子树的左子树结点遍历2向右子树的左子树结点遍历。
对于第一种情况左子树的左子树结点只要其左结点比当前结点小即可。对于第二种情况不仅要求左结点要比当前结点小还要保证不能小过之前的右子树的根结点及其以上的值。

在向右子树遍历时同理也会遇到两种情况
1向右子树的右子树结点遍历2向左子树的右子树结点遍历。
对于第一种情况右子树的右子树结点只要其右结点比当前节点大即可。对于第二种情况不仅要求右结点比当前结点大还要保证不能大过之前的左子树的根结点及其以上的值。

因此我们需要设置两个局部变量maxleft记录当前结点的左子树不可超过的值minright当前结点右子树中的结点不可小于的值。当遍历到左子树结点时更新maxleft向左应更小因此取较小值。当遍历到右子树结点时更新minright向右更大因此取较大值。

/**
 * 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:
    bool res = true;
    // root当前遍历结点、maxleft规定左子树结点不能超过的值minright规定右子树中结点不能小于的值
    void traversal(TreeNode* root, long long maxleft, long long minright) {
        if(!root->left && !root->right)             return ;
        // 处理左的左和右的左
        if(root->left) {
            long long left = root->left->val;
            // 当左子树的值小于当前结点的值若还处于右子树时该结点的值比右子树中不能小于的值大则继续遍历
            if(left < root->val && left > minright) {                
                // 向左子树遍历时更新左子树结点不能超过的值取较小值
                // long long l = root->val < maxleft ? root->val : maxleft;		
                // 这里可以不用再比较因为当向左遍历之前成立时说明当前结点一定小于之前的根节点
                traversal(root->left, root->val, minright);
            } else {
                res = false;
                return ;
            }            
        }
        // 处理右的右和左的右
        if(root->right) {
            long long right = root->right->val;
            // 当右子树的值大于当前结点的值若还处于左子树时该结点的值比左子树中不能超过的值小则继续遍历
            if(right > root->val && right < maxleft) {
                // 向右子树遍历时更新右子树不能小于的值取较大值
                // long long r = root->val > minright ? root->val : minright;		
                // 这里可以不用再比较因为当向右遍历之前成立时说明当前结点一定大于之前的根节点
                traversal(root->right, maxleft, root->val);
            } else {
                res = false;
                return ;
            }
        }

    }
    bool isValidBST(TreeNode* root) {
        // 测试数据中有关INT_MAX和INT_MIN因此用long long
        traversal(root, LONG_MAX, LONG_MIN);
        return res;
    }
};

3后序遍历

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);
    }
};

时间复杂度 $O(n)$
空间复杂度 $O(n)$

二、迭代法

/**
 * 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:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur || !st.empty()) {
            while(cur) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();      st.pop();
            if(pre != NULL && cur->val <= pre-<val)
                return false;
            pre = cur;
            cur = cur->right;            
        }
    }
};

参考文章98.验证二叉搜索树、验证二叉搜索树