Day48 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例1：

输入:
2
/
1 3
输出: true

示例2：

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

Java解法

思路：

• 二叉搜索树每个节点具有共性，因此可以考虑使用递归处理

package sj.shimmer.algorithm.y2021;

import sj.shimmer.algorithm.TreeNode;

/**
 * Created by SJ on 2021/3/14.
 */

class D48 {
    public static void main(String[] args) {
        TreeNode n6 = new TreeNode(6,null,null);
        TreeNode n3 = new TreeNode(3,null,null);
        TreeNode n4 = new TreeNode(4,n3,n6);
        TreeNode n1 = new TreeNode(1,null,null);
        TreeNode n5 = new TreeNode(5,n1,n4);
        System.out.println(isValidBST(n5));
        TreeNode n2 = new TreeNode(2,n1,n3);
        System.out.println(isValidBST(n2));
    }
    public static boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public static boolean isValidBST(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

image

官方解

https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

1. 递归

   如上

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

2. 中序遍历

   二叉搜索树的性质让它在经历中序遍历的时候输出的结果是升序

   所以通过中序遍历来校验结果是否升序

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)