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 js_leetcode题解之98-validate-binary-search-tree.js
python python_leetcode题解之098_Validate_Binary_Search_Tree
c语言基础 c语言_leetcode题解之0098_validate_binary_search_tree.zip
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 ...
* [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]...
- **Validate Binary Search Tree**:验证一个二叉树是否为二叉搜索树。 - **Recover Binary Search Tree**:恢复二叉搜索树中的两个错误节点。 - **Binary Tree Path**:找到二叉树中和为目标值的路径。 - **...
leetcode ...Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ
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...
- Validate Binary Search Tree:验证给定的二叉树是否为有效的二叉搜索树(BST),这需要对二叉树的遍历和树节点值的区间限制有清晰的理解。 - Valid Parentheses:这是一个用来检测字符串中括号是否有效匹配的问题...
本压缩包文件“python-leetcode面试题解之第98题验证二叉搜索树-题解.zip”专注于解决LeetCode的第98题,即“验证二叉搜索树”(Validate Binary Search Tree)。下面我们将深入探讨这个话题,了解如何使用Python来...
25. Validate Binary Search Tree:验证二叉搜索树。 26. Maximum Depth of Binary Tree:计算二叉树的最大深度。 27. Minimum Depth of Binary Tree:计算二叉树的最小深度。 28. Balanced Binary Tree:判断一个...
6. BinaryTree(二叉树): 二叉树是每个节点最多有两个子节点的树数据结构,常用于组织数据,以便进行快速查找、插入和删除。文件中提到的二叉树相关题目包括: - Validate Binary Search Tree(验证二叉搜索树) ...
在本压缩包“php-leetcode题解之验证二叉搜索树.zip”中,主要包含的是使用PHP语言解决LeetCode上的一道题目——验证二叉搜索树(Validate Binary Search Tree)。LeetCode是一个流行的在线编程挑战平台,它提供了...
Validate Binary Search Tree)和判断对称二叉树(101. Symmetric Tree)。这两个问题都涉及到对二叉树结构的深入理解和遍历策略。 首先,我们来看验证二叉搜索树。二叉搜索树(Binary Search Tree, BST)是一种...
- 例如,验证二叉搜索树(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:判断二叉树...
5. **验证二叉搜索树的有效性** (Validate Binary Search Tree) - 验证一个二叉树是否是二叉搜索树,可以通过中序遍历后检查序列是否严格升序来实现。 - 示例代码中,使用迭代中序遍历,在遍历过程中维护一个栈,...
5. **二叉树**:二叉树问题包括遍历、查找、平衡调整等,如"二叉树的最大路径和"(Maximum Path Sum)、"验证二叉搜索树"(Validate Binary Search Tree)。 6. **回溯**:回溯是一种尝试所有可能解的算法策略,...