98. 验证二叉搜索树

题目链接

解题思路

• 这种二叉树的题目，绝大部分可以用「二叉树的递归套路」来解决，那么什么是「二叉树的递归套路」？其实就是每个节点会有信息，该节点信息怎么来的？左儿子的信息 + 右儿子的信息 ，然后加工成自己的信息。
• 根结点是否是搜索二叉树？需要左儿子和右儿子给什么信息？
  • 首先要知道左子树和右子树，是否是搜索二叉树
  • 然后要知道左子树的最大值left_max，以及右子树的最小值right_min，然后根结点val > left_max，同时val < right_min
• 那么，「每个节点的信息」究竟是什么？
  • 注意，对于根节点来说，其左儿子A，是左子树，但是对于A自己来说，A自己就是「根」
  • 也就是说，每个节点，我们要看成是「独立」的，不能认为某个节点是「左子树」，或者是「右子树」，因为我们要递归，当来到某一个递归时，我们根本不知道该节点到底是什么情况。
  • 所以，「每个节点的信息」要保持一致
  • 拿本题来说，我只需要知道左子树的最大值，右子树的最小值，但是，「每个节点的信息」要保持一致，所以我们需要的信息就是：1️⃣以该节点为根，整体是否是搜索二叉树；2️⃣以该节点为根，最大值是什么；3️⃣以该节点为根，最小值是什么
• 我们得到「根的信息」后，直接返回1️⃣即可

代码

/**
 * 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:

    struct Info{
        bool isSearch;   // 是否是搜索二叉树
        int _min;        // 最小值
        int _max;        // 最大值
    };

    bool finish = false;    // 如果发现有一个小子树不是搜索二叉树了  可以提前结束了

    // 保证调用这个函数时，head不等于nullptr
    Info process(TreeNode *head) {
        if (finish) {   // 提前结束了
            return {false, 0, 0};    // 无用值
        }
        bool isSearch = true;
        int _min = head->val;
        int _max = head->val;
        if (head->left != nullptr) {    // 左子树不为空  问左子树要答案
            Info left_info = process(head->left);
            // 这里是一个小加速，如果左子树都不是搜索二叉树了 
            // 以head为头的，肯定也不是搜索二叉树了，其他的信息也没不重要了
            if (left_info.isSearch == false) {
                finish = true;
                return Info{false, _min, _max};
            }
            // 小加速  和上述理由一样
            if (head->val <= left_info._max) {
                finish = true;
                return Info{false, _min, _max};
            }
            _min = left_info._min;    // 更新以head为头的最小值
        }

        if (head->right != nullptr) {
            Info right_info = process(head->right);
            if (right_info.isSearch == false) {
                finish = true;
                return Info{false, _min, _max};
            }
            if (head->val >= right_info._min) {
                finish = true;
                return Info{false, _min, _max};
            }
            _max = right_info._max;
        }
        return Info(isSearch, _min, _max);
    }

    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        Info ans = process(root);
        return ans.isSearch;
    }
};