leetcode：98. 验证二叉搜索树

题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

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

示例 1：
[中等] 98. 验证二叉搜索树 - 图1

  1. 输入：root = [2,1,3]
  2. 输出：true

示例 2：
[中等] 98. 验证二叉搜索树 - 图2

  1. 输入：root = [5,1,4,null,null,3,6]
  2. 输出：false
  3. 解释：根节点的值是 5 ，但是右子节点的值是 4 。

解答 & 代码

本题的正确解法是通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉搜索树算法的一个小技巧。

思想：递归遍历每个节点的同时，缩小每个节点的值应满足的上下界，如果是二叉搜索树，就必须每个值都在其上下界内

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     /* 限定以 root 为根节点的子树必须满足 minVal < root->val < maxVal */
  15.     bool dfsValidBST(TreeNode* root, long long minVal, long long maxVal)
  16.     {
  17.         // 递归结束条件
  18.         if(root == nullptr)
  19.             return true;
  20.         // 返回以 root 为根的树是否是二叉搜索树
  21.         return root->val > minVal && root->val < maxVal &&    // 1. 判断 root 是否满足 minVal < root->val < maxVal
  22.             dfsValidBST(root->left, minVal, root->val) &&    // 2. 递归判断左子树是否是二叉搜索树
  23.             dfsValidBST(root->right, root->val, maxVal);    // 3. 递归判断右子树是否是二叉搜索树
  24.     }
  25. public:
  26.     bool isValidBST(TreeNode* root) {
  27.         return dfsValidBST(root, LONG_MIN, LONG_MAX);
  28.     }
  29. };

复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(log N)：递归深度 = 二叉树高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 97.16% 的用户
  4. 内存消耗：21.2 MB, 在所有 C++ 提交中击败了 33.00% 的用户