验证二叉搜索树

原题：

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

  1. 输入:
  2.     2
  3.    / \
  4.   1   3
  5. 输出: true

示例 2:

  1. 输入:
  2.     5
  3.    / \
  4.   1   4
  5.      / \
  6.     3   6
  7. 输出: false
  8. 解释: 输入为: [5,1,4,null,null,3,6]。
  9.      根节点的值为 5 ，但是其右子节点值为 4 。

解题方法：

解法一：

  1. class Solution {
  2. public:
  3.     long long maxval;
  4.     long long minval;
  5.     bool isValidBST(TreeNode* root) {
  6.         if(!root) return true;
  7.         maxval=LLONG_MIN;
  8.         minval=LLONG_MAX;
  9.         return (maxOfLeft(root->left)<root->val)&&(minOfRight(root->right)>root->val)&&isValidBST(root->left)&&isValidBST(root->right);
  10.     }
  13.     long long maxOfLeft(TreeNode* left)
  14.     {
  15.         if(!left) return maxval;
  16.         maxOfLeft(left->left);
  17.         maxOfLeft(left->right);
  18.         maxval=max((long long)left->val,maxval);
  19.         return maxval;
  20.     }
  22.     long long minOfRight(TreeNode* right)
  23.     {
  24.         if(!right) return minval;
  25.         minOfRight(right->left);
  26.         minOfRight(right->right);
  27.         minval=min((long long)right->val,minval);
  28.         return minval;
  29.     }
  30. };

解法二：

class Solution {
public:
    long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;

        bool left = isValidBST(root->left);
        // 中序遍历，验证遍历的元素是不是从小到大
        if (maxVal < root->val) maxVal = root->val;
        else return false;
        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;
    }
};

做题小结：

针对解法一：

  1. 首先要注意[5,1,6,null,null,3,7]这样的测试用例，虽然对于每个单独的结点来说，他的左节点和右节点满足条件，但是他的左子树和右子树不一定满足，因此我的思路应该是对于每个节点，找出其左子树的最大值和右子树的最小值来进行比较，依次验证。
  2. 然后就要注意minval，maxval是不能回溯的，不然就无法找出整个子树的最大最小值，但是在遍历每个单独节点前，又必须对他们重新赋值，因此他们的位置应该在将要遍历下一个结点之前。
  3. 最后就是最折磨人的地方了，INT_MAX和LON_G__MAX都表示2147483647，INT_MIN和LONG_MIN都表示-2147483647 - 1，必须用到LLONG_MAX,LLONG_MIN来表示才能去pass掉测试用例中2147483647和-2147483647 - 1的用例。同时也需要注意在声明或者返回值的地方都要改成long long，max，min函数中也必须是两个long long值才会返回long long

针对解法二：

  1. 解法二就要聪明很多了，不需要对每个节点挨个判断最大最小值，只需要中序遍历，看是不是从小到大的顺序就足够了

针对解法三：

  1. 使用一个有序数组，直接把二叉树按照中序遍历的顺序放入数组中，最后判断该数组是否有序就可以了
  2. 一定要灵活运用二叉搜索树的中序遍历是从小到大的次序的性质。