题解 | 验证二叉搜索树

题干解析:

检验一棵树是否为二叉树,检验成功则返回true,不成功则为false

有效 二叉搜索树定义如下：

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

针对二叉树搜索树有一个众所周知的结论(不知道的现在就知道了):

• 对二叉搜索树进行中序遍历得到的节点值数组为严格递增数组.

应用此结论,题目就变成了中序遍历此树,遍历的同时判断序列是否严格递增

算法思路:

递归中序遍历,每次与前一个节点最大值进行比较,如果大于则继续递归,小于则结束递归,返回false

实现代码:

/**
 * 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 {
private:
    bool ans = true;
    long long _max = -2147483649; // 题设范围最小值为-2147483648

    void dfs(TreeNode *node) {
        if (node && ans) {
            dfs(node->left);
            if (_max >= node->val) ans = false;
            else _max = node->val;
            dfs(node->right);
        }
    }
public:
    bool isValidBST(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

复杂度分析:

针对具有n个节点的二叉树:

• 遍历每个节点并进行比较操作,时间复杂度为O(n)
• 每个节点递归执行一次,空间复杂度最高为O(n)(二叉树退化为一条链)