`

Leetcode - 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.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

[分析] 这题较一年之前的版本多了些边界值的test case,看出leetcode在不断优化完善,赞!
对我来说,对边界条件的考虑是bug free的关键。基本思路,判断根节点是否满足条件,然后递归判断左右子节点是否满足条件。判断是否满足BST性质,可以从根节点下传节点的值域,root的初始值域是多少呢,(Integer.MIN_VALUE, Integer.MAX_VALUE)貌似是一个合理的选择,但如果root本身就是Integer.MIN_VALUE或者是Intger.MAX_VALUE呢? 因此还需要使用两个辅助flag,effLowBound, effUpBound分别表示值域的上下边界是否有效,对于root,上下边界均无效。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE, false, false);
    }
    public boolean check(TreeNode curr, int low, int up, 
            boolean effLowBound, boolean effUpBound) {
        if (curr == null) return true;
        if ((effLowBound && curr.val <= low) || (effUpBound && curr.val >= up))
            return false;
        return check(curr.left, low, curr.val, effLowBound, true)
                && check(curr.right, curr.val, up, true, effUpBound);
    }
}
分享到:
评论

相关推荐

    js-leetcode题解之98-validate-binary-search-tree.js

    js js_leetcode题解之98-validate-binary-search-tree.js

    python-leetcode题解之098-Validate-Binary-Search-Tree

    python python_leetcode题解之098_Validate_Binary_Search_Tree

    c语言-leetcode题解之0098-validate-binary-search-tree.zip

    c语言基础 c语言_leetcode题解之0098_validate_binary_search_tree.zip

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    Leetcode题目+解析+思路+答案.pdf

    - **Validate Binary Search Tree**:验证一个二叉树是否为二叉搜索树。 - **Recover Binary Search Tree**:恢复二叉搜索树中的两个错误节点。 - **Binary Tree Path**:找到二叉树中和为目标值的路径。 - **...

    leetcode跳跃-leetcode:leetcode一天一次

    leetcode ...Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ

    javalruleetcode-what_the_dead_men_say:what_the_dead_men_say

    Validate Binary Search Tree - Java Recursive - Java Iterative - Java Inorder 0099 Recover Binary Search Tree - Java Recursive 0101 Symmetric tree - Java Recursive - Java Iterative - C Recursive...

    LeetCode各公司题目合集

    - Validate Binary Search Tree:验证给定的二叉树是否为有效的二叉搜索树(BST),这需要对二叉树的遍历和树节点值的区间限制有清晰的理解。 - Valid Parentheses:这是一个用来检测字符串中括号是否有效匹配的问题...

    python-leetcode面试题解之第98题验证二叉搜索树-题解.zip

    本压缩包文件“python-leetcode面试题解之第98题验证二叉搜索树-题解.zip”专注于解决LeetCode的第98题,即“验证二叉搜索树”(Validate Binary Search Tree)。下面我们将深入探讨这个话题,了解如何使用Python来...

    Leetcode book刷题必备

    25. Validate Binary Search Tree:验证二叉搜索树。 26. Maximum Depth of Binary Tree:计算二叉树的最大深度。 27. Minimum Depth of Binary Tree:计算二叉树的最小深度。 28. Balanced Binary Tree:判断一个...

    CleanCodeHandbook_v1.0.3

    6. BinaryTree(二叉树): 二叉树是每个节点最多有两个子节点的树数据结构,常用于组织数据,以便进行快速查找、插入和删除。文件中提到的二叉树相关题目包括: - Validate Binary Search Tree(验证二叉搜索树) ...

    php-leetcode题解之验证二叉搜索树.zip

    在本压缩包“php-leetcode题解之验证二叉搜索树.zip”中,主要包含的是使用PHP语言解决LeetCode上的一道题目——验证二叉搜索树(Validate Binary Search Tree)。LeetCode是一个流行的在线编程挑战平台,它提供了...

    LeetCode 精选 TOP 面试题(3)1

    Validate Binary Search Tree)和判断对称二叉树(101. Symmetric Tree)。这两个问题都涉及到对二叉树结构的深入理解和遍历策略。 首先,我们来看验证二叉搜索树。二叉搜索树(Binary Search Tree, BST)是一种...

    leetcode java

    - 例如,验证二叉搜索树(Validate Binary Search Tree)需要判断给定的二叉树是否符合二叉搜索树的定义。 - 计算二叉树的最大深度(Maximum Depth of Binary Tree)考察递归的使用。 - 平衡二叉树(Balanced Binary...

    常见算法题答案及解析

    25. Validate Binary Search Tree:验证二叉搜索树的合法性。 26. Maximum Depth of Binary Tree:二叉树的最大深度。 27. Minimum Depth of Binary Tree:二叉树的最小深度。 28. Balanced Binary Tree:判断二叉树...

    手稿_V1.031

    5. **验证二叉搜索树的有效性** (Validate Binary Search Tree) - 验证一个二叉树是否是二叉搜索树,可以通过中序遍历后检查序列是否严格升序来实现。 - 示例代码中,使用迭代中序遍历,在遍历过程中维护一个栈,...

    LeetCode:LeetCode上一些算法的解答

    5. **二叉树**:二叉树问题包括遍历、查找、平衡调整等,如"二叉树的最大路径和"(Maximum Path Sum)、"验证二叉搜索树"(Validate Binary Search Tree)。 6. **回溯**:回溯是一种尝试所有可能解的算法策略,...

Global site tag (gtag.js) - Google Analytics