98. 验证二叉搜索树

二叉搜索树的左子树的所有值都小于根节点的值，右子树的值都大于根节点的值
，所以不能通过比较根节点和左右节点的值来判断是否是二叉树搜索树
二叉搜索树的中序遍历为升序，中序遍历后判断数组是否是升序即可判断是否为二叉搜索树

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

递归时用一个pre记录前一个结点，中序遍历是比较pre和当前结点的值，若不符合条件就返回flase

  2. class Solution {
  3. public:
  4.      TreeNode* pre = NULL;
  5.     bool isValidBST(TreeNode* root) {
  6.         if(!root)return true;
  7.         bool left = isValidBST(root->left);
  8.         if(pre!=NULL && root->val<=pre->val)return false;
  9.         pre = root;
  10.         bool right = isValidBST(root->right);
  11.         return left&&right;
  12.     }
  13. };