leetcode 链接：合法二叉搜索树
《程序员面试代码指南》by 左程云 中相关题目：★★☆☆找到二叉树中的最大搜索二叉树（树形dp套路）

题目

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例：

  1. 输入: [2,1,3]
  2.     2
  3.    / \
  4.   1   3
  5. 输出: true
  1. 输入: [5,1,4,null,null,3,6]
  2.     5
  3.    / \
  4.   1   4
  5.      / \
  6.     3   6
  7. 输出: false
  8. 解释: 输入为: [5,1,4,null,null,3,6]。
  9.      根节点的值为 5 ，但是其右子节点值为 4 。

注意如下特殊情形：

  1. 输入: [1,1]
  2.     1
  3.    /
  4.   1
  5. 输出: false
  1. 输入: [2147483647]
  2.     2147483647
  3. 输出: true
  1. 输入: [-2147483648]
  2.     -2147483648
  3. 输出: true

解答 & 代码

解法一：

想法：如果以 root 节点为根节点的树是二叉搜索树，那么要求它的左子树是二叉搜索树、右子树是二叉搜索树，且左子树的最大值小于 root 的值，右子树的最小值大于 root 的值

设置一个 ReturnType 结构作为返回的结构，得到以 root 节点为根节点的树的一些信息，里面包含以 root 节点为根节点的树中的最小节点值 minVal、最大节点值 maxVal 以及该树是否为二叉搜索树 isBST

设置 ReturnType posOrderProcess(TreeNode* root) 函数，进行递归 后序遍历，以得到以 root 节点为根节点的树中的最小节点值 minVal、最大节点值 maxVal 以及该树是否为二叉搜索树 isBST ：

  • 递归结束条件：root 为 NULL，则返回 ReturnType(minVal=(long long)INT_MAX + 1, maxVal=(long long)INT_MIN - 1, isBST=true)
  • 递归得到 root 左子树的信息
  • 递归得到 root 右子树的信息
  • 计算以 root 节点为根节点的树中的最小的节点值：比较左子树的的最小值、右子树的最小值和 root 的值
  • 计算以 root 节点为根节点的树中的最大的节点值：比较左子树的的最大值、右子树的最大值和 root 的值
  • 如果左子树的最大值小于 root 的值，且右子树的最大值大于 root 的值，且左子树是二叉搜索树，且右子树是二叉搜索树，那么以 root 节点为根节点的树是二叉搜索树，返回其信息
  • 否则，以 root 节点为根节点的树不是二叉搜索树，返回其信息

注意：本题有几个需要额外关注的输入样例

  • 输入: [2147483647]，输出 true：INT_MAX = 2147483647，因此在递归结束条件中，不能将返回值的 minVal 设为 INT_MAX ，否则回到上层递归比较，发现右子树的最小值（INT_MAX ）等于 root 的值（2147483647），于是错误判定这棵树不是二叉搜索树
    • 并且不能直接将判定条件改成小于等于：“如果左子树的最大值小于等于 root 的值，且右子树的最大值大于等于 root 的值，且左子树是二叉搜索树，且右子树是二叉搜索树，那么以 root 节点为根节点的树是二叉搜索树”，因为还有输入为 [1, 1] 的情况，答案判定为 false，也就是说该题还要求左子树的值严格小于 root 的值，且严格小于右子树的值，而不能相等
  • 输入: [-2147483648]，输出 true：INT_MIN = -2147483648，和上面类似，在递归结束条件中，不能将返回值的 maxVal 设为 INT_MIN ，否则回到上层递归比较，发现左子树的最大值（INT_MIN ）等于 root 的值（-2147483648），于是错误判定这棵树不是二叉搜索树
  • 输入: [1,1]，输出 false：也就是要求左子树的值严格小于 root 的值，且严格小于右子树的值，而不能相等，才算二叉搜索树

解决方法：将 int 改为 long long（不能是 long，long 的取值范围和 int 相同）；且在递归结束条件中，将返回值的 minVal 设为 INT_MAX + 1 ，将返回值的 maxVal 设为 INT_MIN - 1

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. struct ReturnType {
  11.     long long minVal;
  12.     long long maxVal;
  13.     bool isBST;
  14.     ReturnType(long minV, long maxV, bool BST): minVal(minV), maxVal(maxV), isBST(BST) {}
  15. };
  16. class Solution {
  17. private:
  18.     ReturnType posOrderProcess(TreeNode* root) {
  19.         if(root == NULL)
  20.             return ReturnType((long long)INT_MAX + 1, (long long)INT_MIN - 1, true);
  22.         ReturnType lData = posOrderProcess(root->left);
  23.         ReturnType rData = posOrderProcess(root->right);
  25.         long long minVal = (lData.minVal < rData.minVal) ? lData.minVal : rData.minVal;
  26.         minVal = (minVal < root->val) ? minVal : root->val;
  27.         long long maxVal = (lData.maxVal > rData.maxVal) ? lData.maxVal : rData.maxVal;
  28.         maxVal = (maxVal > root->val) ? maxVal : root->val;
  29.         if(lData.isBST && rData.isBST && lData.maxVal < root->val && rData.minVal > root->val)
  30.             return ReturnType(minVal, maxVal, true);
  31.         else
  32.             return ReturnType(minVal, maxVal, false);
  33.     }
  34. public:
  35.     bool isValidBST(TreeNode* root) {
  36.         return posOrderProcess(root).isBST;
  37.     }
  38. };

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 85.77% 的用户
内存消耗：21.2 MB, 在所有 C++ 提交中击败了 13.79% 的用户

解法二：

以 root 节点为根的树是二叉搜索树，只有几种情形：

  • root == NULL
  • root 节点不为 NULL，左子树若不为空则左子树的值都小于 root 的值；右子树若不为空则右子树的值都大于 root 的值

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

因此，设置一个辅助的递归函数 bool isBST(TreeNode* root, long long min, long long max) 来判断以 root 节点为根的树是否为二叉搜索树

  • 如果 root == NULL ，则是二叉搜索树，直接返回 true
  • 否则，需要先判断 root 的值是否在区间 (min, max) 内，注意是开区间，min、max 分别是 root 节点值（or 以 root 节点为根的树）的上下界
    • 如果不在区间内，则不是二叉搜索树，返回 false
    • 如果在区间内，还需要继续缩小区间范围，递归判定其左子树的值是否在新的区间 (min, root->val) 内，以及其右子树的值是否在新的区间 (root->val, max) 内，如果满足条件，则是二叉搜索树，返回 true；否则不是二叉搜索树，返回 false
      /**
* 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 {
private:
bool isBST(TreeNode* root, long long min, long long max)
{
   return (root == NULL) ||
           ((root->val > min) && (root->val < max) && isBST(root->left, min, root->val) && isBST(root->right, root->val, max));
}
public:
bool isValidBST(TreeNode* root) {
   return isBST(root, LONG_MIN, LONG_MAX);
}
};
      执行结果： ``` 执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 61.73% 的用户 内存消耗：21 MB, 在所有 C++ 提交中击败了 58.78% 的用户 ```