题目描述

给定一棵二叉树，判断它是否是一棵合法的二叉搜索树(BST)。

二叉搜索树需要满足如下条件：

• 左子树的所有节点的值都小于当前节点的值；
• 右子树的所有节点的值都大于当前节点的值；
• 左子树和右子树都必须是合法的二叉搜索树；

样例1

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

样例2

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

算法

(深度优先遍历) $O(n)$

深度优先遍历整棵子树。
遍历时，需要向上传递当前子树中的最小值和最大值，这里可以用C++中的引用来专递。
对于当前节点，我们先遍历它的左子树，判断左子树是否合法，同时判断左子树的最大值是否小于当前节点的值；然后遍历右子树，判断右子树是否合法，同时判断右子树的最小值是否大于当前节点的值。
如果条件均满足，说明以当前节点为根的子树是一棵合法的二叉搜索树，返回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 maxv, minv;
        return dfs(root, maxv, minv);
    }

    bool dfs(TreeNode* root, int &maxv, int &minv)
    {
        maxv = minv = root->val;
        if (root->left)
        {
            int nowMaxv, nowMinv;
            if (!dfs(root->left, nowMaxv, nowMinv))
                return false;
            if (nowMaxv >= root->val)
                return false;
            maxv = max(maxv, nowMaxv);
            minv = min(minv, nowMinv);
        }
        if (root->right)
        {
            int nowMaxv, nowMinv;
            if (!dfs(root->right, nowMaxv, nowMinv))
                return false;
            if (nowMinv <= root->val)
                return false;
            maxv = max(maxv, nowMaxv);
            minv = min(minv, nowMinv);
        }
        return true;
    }
};