题目链接

LeetCode

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1
  

  解题思路

  方法一：递归

    我们设计一个递归函数 **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 表示一个无穷大的值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root,long lower, long upper) {
        if(root==null){
            return true;
        }
        if(root.val <= lower || root.val >= upper){
            return false;
        }
        return isValidBST(root.left,lower,root.val) && isValidBST(root.right,root.val,upper);
    }
}

• 时间复杂度 O(n)

• 空间复杂度 O(n)

  方法二：中序遍历

  中序遍历应为递增

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode() {}
  *     TreeNode(int val) { this.val = val; }
  *     TreeNode(int val, TreeNode left, TreeNode right) {
  *         this.val = val;
  *         this.left = left;
  *         this.right = right;
  *     }
  * }
  */
  class Solution {
    private boolean res = true;
    public boolean isValidBST(TreeNode root) {
        Deque<Integer> stack = new LinkedList<>();
        recur(root,stack);
        return res;
    }
    private void recur(TreeNode root,Deque<Integer> stack) {
        if(!res || root == null){
            return;
        }
        recur(root.left,stack);
        if(!stack.isEmpty()&&stack.peek()>=root.val){
            res = false;
            return;
        }
        stack.push(root.val);
        recur(root.right,stack);
    }
  }
  

• 时间复杂度 O(n)

• 空间复杂度 O(n)