题目内容

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

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

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

示例

示例 1:

输入:
2
/ \
1 3
输出: true

示例 2:

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

题解

本题有两种思路，第一个思路就是按照定义判断，第二个思路就是对该二叉树进行中序遍历，然后判断输出是否有序即可。

在第一个思路中，需要求解左子树中的最大值和右子树中的最小值，然后与根节点进行比较，如果每次递归中，左子树的最大值均小于根节点小于右子树的最小值，则说明是一颗二叉搜索树。

在第二个思路中，如果中序遍历有序，那么一定可以推出其为一个二叉搜索树。在中序遍历中，一定是先输出左子树，然后输出根节点，然后再输出右子树，如果有序则一定说明左子树小于根节点小于右子树，因此一定是一颗二叉搜索树。

代码

/**
 * 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) {
      if(!root) return true;//如果当前子树为空，返回true
      return dfs(root)[0];//
    }
  	vector<int> dfs(TreeNode* root){
      //定义一个结果向量，存放状态，当前子树最小值，当前子树最大值
      vector<int> res({1,root->val,root->val});
      //如果存在左子树
      if(root->left){
        //判断左子树是否有问题
        auto t = dfs(root->left);
        //如果左子树有问题或者子树的最大值大于等于根节点的值
        if(!t[0]||t[2]>=root->val)res[0] = 0;
        res[1] = min(res[1],t[1]);//更新最小值
        res[2] = max(res[2],t[2]);//更新最大值
      }
      //如果存在右子树
      if(root->right){
        auto t = dfs(root->right);
        //如果右子树有问题或者右子树最小值大于等于根节点的值
        if(!t[0] || t[1] <= root->val) res[0]=0;
        res[1] = min(res[1],t[1]);//更新最小值
        res[2] = max(res[2],t[2]);//更新最大值
      }
      return res;
    }
};