问题

给定一个二叉树，判断其是否是一个有效的二叉搜索树
假设一个二叉搜索树具有如下特征：

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

示例 1:
输入:
2
/ \
1 3
输出: true

示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]，根节点的值为5，但是其右子节点值为4

解法一：递归

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

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
  4.     }
  6.     public boolean isValidBST(TreeNode node, long lower, long upper) {
  7.         if (node == null) {
  8.             return true;
  9.         }
  10.         if (node.val <= lower || node.val >= upper) {
  11.             return false;
  12.         }
  13.         return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
  14.     }
  15. }
  • 时间复杂度 : leetcode-98：验证二叉搜索树 - 图1，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次
  • 空间复杂度 : leetcode-98：验证二叉搜索树 - 图2，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层

方法二：迭代

二叉搜索树中序遍历得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是

  1. class Solution{
  2.     public boolean isValidBST(TreeNode root){
  3.         Deque<TreeNode> stack = new LinkedList<TreeNode>();
  4.         double inorder = -Double.MAX_VALUE;
  6.         while(!stack.isEmpty() || root != null){
  7.             while(root != null){
  8.                 stack.push(root);
  9.                 root = root.left;
  10.             }
  11.             stack.pop(root); //关键
  12.             if(root.val <= inorder){
  13.                 return false;
  14.             }
  15.             inorder = root.val;
  16.             root = root.right; // 关键
  17.         }
  18.         return true;
  19.     }
  20. }
  • 时间复杂度 : leetcode-98：验证二叉搜索树 - 图3，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次
  • 空间复杂度 : leetcode-98：验证二叉搜索树 - 图4，其中 n 为二叉树的节点个数。栈最多存储 n 个节点