题目描述

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

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

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

样例

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

算法

(递归)

大部分参考了y总的题解
1. 使用DFS遍历整棵子树。
2. 遍历的时候，需要传递当前子树中的最大值maxe和最小值mine。所以用到了引用&。
3. 对于当前节点，先遍历它的左子树，判断左子树是否合法。同时判断左子树的最大值是否小于当前节点的值。
4. 接下来，遍历右子树，判断右子树是否合法。同时判断右子树的最小值是否大于当前节点的值。
5. 如果3 4的条件都满足，说明以当前节点为根的子树是一棵合法的BST，return true即可。

时间复杂度

$O(n)$

C++ 代码

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

    /*
    bool dfs(int r, TreeNode *p, TreeNode *q)
    {
        if(!p || !q) return !p;
        if(p->val > r) return false;
        if(q->val < r) return false;
        return dfs(p->val, p->left, p->right) && dfs(q->val, q->left, q->right);
    }
    */

    bool dfs(TreeNode *root, int &maxe, int &mine)
    {
        maxe = mine = root->val;
        if(root->left)
        {
            int nmax, nmin;
            if(!dfs(root->left, nmax, nmin)) return false;
            if(nmax >= root->val) return false;
            maxe = max(maxe, nmax);
            mine = min(mine, nmin);
        }

        if(root->right)
        {
            int nmax, nmin;
            if(!dfs(root->right, nmax, nmin)) return false;
            if(nmin <= root->val) return false;
            maxe = max(maxe, nmax);
            mine = min(mine, nmin);
        }
        return true;
    }
};