devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【每日力扣28】验证二叉搜索树_验证 叉搜索树 给你 个 叉树的根节点 root ,判断其是否是 个有效的

作者：羊村懒王 | 2024-03-12 07:37:02

赞

踩

验证 叉搜索树 给你 个 叉树的根节点 root ,判断其是否是 个有效的

一、题目[LeetCode-98]

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

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

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

示例 1：

输入：root = [2,1,3]

输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]

输出：false

解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

二、思路

递归：（后序遍历）

递归到每一个节点时，考虑四种情况：没有儿子的节点返回true；只有左儿子的节点判断是否小于父亲值；只有右儿子的节点判断是否大于父亲值；有两个儿子的节点则判断是否满足BST要求。

再结合后续遍历的一般思路：先遍历再操作（这里是判断大小，返回bool值），写出如下代码

  1. class Solution {
  2. public:
  3.     bool isValidBST(TreeNode* root) {
  4.         if (root->left == nullptr && root->right == nullptr)//(1)节点没有儿子的退化情况
  5.             return true;
  6.         if (root->left != nullptr && root->right == nullptr)//(2)节点只有左儿子的退化情况
  7.         {
  8.             if (isValidBST(root->left))
  9.                 return root->left->val < root->val;
  10.             else return false;
  11.         }
  12.         if (root->left == nullptr && root->right != nullptr)//(3)节点只有右儿子的退化情况
  13.         {
  14.             if (isValidBST(root->right))
  15.                 return root->right->val > root->val;
  16.             else return false;
  17.         }
  18.         else//(4)节点两个儿子都有的一般情况
  19.         {
  20.             if (isValidBST(root->left) && isValidBST(root->right))
  21.                 return (root->left->val < root->val) && (root->right->val > root->val);
  22.             else return false;
  23.         }
  24.     }
  25. };

但是这是错误的。没有考虑到如下情况

 

 

这里虽然3小于6通过了判断，但是3在根节点右边，应当满足大于根节点5，因此该算法是错误的。

递归：（先序遍历）

这里换一种递归方式。当遍历到每个节点时，先对该节点判断，值是否在正确的范围中，不符合则返回false，符合则继续递归深入向后面的节点继续判断。

  • 对于节点A的左儿子B，B的范围是(A的下限, A.val)
  • 对于节点A的右儿子C，C的范围是(C.val, A的上限)

上一种思路的问题便在于忽视了B有个下限——A的最下限，和C有个上限——A的上限。问题的难点便在于，如果使用递归法，当遍历到子节点B时，如何能够保存有父节点A的下限值。

这里提供一个方法：重载isValidBST()方法，在参数列表里加上两个变量，low和high，分别表示判断该节点的上限和下限。当递归到A时，假设A的下限是ALow，上限是AHigh，对于做儿子B，递归的时候，将参数high由原来的AHigh更改为A.val，而参数low仍然是A的下限ALow。这样就做到了保存父节点的下限值继续用于左儿子B的判断。

一开始是判断根节点，对于根节点的取值范围自然是没有限制的。但是为了保持算法的统一性，用重载子方法判断根节点时，依然用到后两个参数low和high。这里将low设为INT_MIN，high设为INT_MAX即可。

这里先写一个一开始遇到的典型错解。

  1. class Solution {
  2. public:
  3.     bool isValidBST(TreeNode* root) {
  4.         return isValidBST(root, INT_MIN, INT_MAX);
  5.     }
  6.  
  7.     bool isValidBST(TreeNode* root, int low, int high) {//重载子方法，用于对每个节点统一性的递归
  8.         if (root->val < low || root->val > high)//先序遍历先对节点操作再递归。先对节点判断是否在符合的范围内。
  9.             return false;
  10.         if (root->left != nullptr)//如果有左儿子，
  11.             return isValidBST(root->left, low, root->val);//递归分析左儿子。左儿子下限是父亲的下限，上限是父亲的值。
  12.         if (root->right != nullptr)//如果有右儿子，
  13.             return isValidBST(root->right, root->val, high);//递归分析右儿子。右儿子下限是父亲的值，上限是父亲的上限。
  14.         return true;
  15.     }
  16. };

 看似所有情况都考虑到位，但是写法上有严重错误。这段代码会发生“在还未遍历完右子树就直接提前return”的问题。因为

  1. if (root->left != nullptr)//
  2.             return isValidBST(root->left, low, root->val);

这行是判断左子树是否符合要求。但是这里写了一个“return”，判断完左子树就直接return结果，后面一行判断右子树的代码无法运行。也正如本例

判断完左子树1->3->6后直接返回了true，而未来得及判断右子树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. public:
  14.     bool isValidBST(TreeNode* root) {
  15.         return isValidBST(root, LONG_MIN, LONG_MAX);
  16.     }
  17.  
  18.     bool isValidBST(TreeNode* root, long int low, long int high) {//重载子方法，用于对每个节点统一性的递归
  19.         if (root == nullptr)//空节点的退化情况
  20.             return true;
  21.         if (root->val <= low || root->val >= high)//先序遍历先对节点操作再递归。先对节点判断是否在符合的范围内。
  22.             return false;
  23.         return isValidBST(root->left, low, root->val) && isValidBST(root->right, root->val, high);//递归分析左儿子。左儿子下限是父亲的下限，上限是父亲的值。
  24.         //再递归分析右儿子。右儿子下限是父亲的值，上限是父亲的上限。
  25.     }
  26. };

三、官方题解（来源：力扣（LeetCode））

方法一: 递归（同上述方法）

要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用，由题目给出的信息我们可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

  1. class Solution {
  2. public:
  3.     bool helper(TreeNode* root, long long lower, long long upper) {
  4.         if (root == nullptr) {
  5.             return true;
  6.         }
  7.         if (root -> val <= lower || root -> val >= upper) {
  8.             return false;
  9.         }
  10.         return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
  11.     }
  12.     bool isValidBST(TreeNode* root) {
  13.         return helper(root, LONG_MIN, LONG_MAX);
  14.     }
  15. };
  16.  
  17. 作者：LeetCode-Solution
  18. 链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
  19. 来源：力扣（LeetCode）
  20. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

  • 时间复杂度 : O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
  • 空间复杂度 : O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n) 。

方法二：中序遍历（迭代实现——栈）

基于方法一中提及的性质，我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是，下面的代码我们使用栈来模拟中序遍历的过程。

  1. class Solution {
  2. public:
  3.     bool isValidBST(TreeNode* root) {
  4.         stack<TreeNode*> stack;
  5.         long long inorder = (long long)INT_MIN - 1;
  6.  
  7.         while (!stack.empty() || root != nullptr) {
  8.             while (root != nullptr) {
  9.                 stack.push(root);
  10.                 root = root -> left;
  11.             }
  12.             root = stack.top();
  13.             stack.pop();
  14.             // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
  15.             if (root -> val <= inorder) {
  16.                 return false;
  17.             }
  18.             inorder = root -> val;
  19.             root = root -> right;
  20.         }
  21.         return true;
  22.     }
  23. };
  24.  
  25. 作者：LeetCode-Solution
  26. 链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
  27. 来源：力扣（LeetCode）
  28. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

  • 时间复杂度 : O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
  • 空间复杂度 : O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n) 的空间。

四、学习心得

通过这道题对于树的遍历有了更深入的理解

先序遍历：对于每个节点先操作再遍历左右儿子

中序遍历：对于每个节点先遍历左儿子再操作再遍历右儿子

后序遍历：对于每个节点先遍历左右儿子再操作

可以用递归和迭代两种方式实现，递归更为形象，遍历的过程更为明显；迭代则常用到栈维护节点访问顺序。

参见清华大学邓俊辉《数据结构》，其中对于树的遍历的实现有详细的说明。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/223030
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号