脚本宝典收集整理的这篇文章主要介绍了[Leetcode] Validate Binary Search Tree 验证二叉搜索树，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Validate Binary SeArch Tree

Given a binary tree, determine if IT is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left suBTree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

递归法

复杂度

时间 O(N) 空间 O(H) 递归栈空间

思路

递归的判断每个节点是否满足BST的要求，需要注意的是BST的要求不只是左节点小于根节点小于右节点，还有个隐含的条件是，左子树里所有节点都要小于根节点，而右子树里所有节点都要大于根节点。所以我们要把这个上限和下限代入递归中。

注意

• 这里的结构和不同的二叉树遍历一样，如果到空节点就返回，否则递归遍历左节点和右节点。唯一不同是加入了max和min，所以要在递归之前先判断是否符合max和min的条件。

• 不用再额外判断左右节点和根节点的关系，因为我们加入了max和min，如果左节点大于根节点的话，下一轮就过不了max的检查，右节点和min同理。

代码

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    PRivate boolean isValidBST(TreeNode root, Integer max, Integer min){
        if(root == null){
            return true;
        }
        // 如果该节点大于上限 返回假
        if(max != null && root.val >= max){
            return false;
        }
        // 如果该节点小于下限 返回假
        if(min != null && root.val <= min){
            return false;
        }
        // 递归判断左子树和右子树
        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val);
    }
}

脚本宝典总结

以上是脚本宝典为你收集整理的[Leetcode] Validate Binary Search Tree 验证二叉搜索树全部内容，希望文章能够帮你解决[Leetcode] Validate Binary Search Tree 验证二叉搜索树所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。