This problem killed me once. the tricky thing is that only judging parent node greater than left child and less than right child is NOT enough. you need to make sure that the right most leave of your right subtree is also less than current node. A fake example is
10
/
5
\
12
public boolean isBST() {
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBST(TreeNode node, int minValue, int maxValue) {
if (node == null) return true;
if (node.data < minValue || node.data > maxValue) {
return false;
}
boolean isBst = true;
if (node.left != null) {
isBst &= isBST(node.left, minValue, node.data);
if (!isBst)
return false;
}
if (node.right != null) {
isBst &= isBST(node.right, node.data, maxValue);
if (!isBst)
return false;
}
return true;
}
分享到:
相关推荐
在IT领域,排序二叉树是一种特殊的二叉树数据结构,它的每个节点的值都大于其左子树中任意节点的值...通过分析“verify-complete-binary-tree.cpp”的源代码,我们可以深入理解这些概念,并学习如何在实践中应用它们。
Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. Recover Binary Search Tree 109. Convert Sorted List to Binary Search Tree 116. Populating Next Right ...
* [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]...
The FreeBSD release tree 4-3. The overall development model 5-1. Overview of official hats 6-1. Process summary: adding a new committer 6-2. Process summary: removing a committer 6-3. Process summary...
Upon installation, the entire system, excluding a small start-up script, resides within a single directory tree. The location of this directory can be chosen freely by the installer, without needing ...
merge while leaving the working tree and the index still in a mess. * "git format-patch" learns a configuration to set the default for its --notes=<ref> option. * The code to show args with ...
To guarantee uniqueness, they should be based on the full path in a project's source tree. For example, the file foo/src/bar/baz.h in project foo should have the following guard: #ifndef FOO_BAR_BAZ...
option to restore this directory tree or you will have problems because the files would not be in their proper subdirectories. Please note most of these directories are differently named to ICS V7 ...
Fixed problem with NodeAdd from another tree (Document reference gets updated now) ! Fixed deletion of empty attributes Version 2.36 (11Nov2007) ! Do not save empty encoding (e.g. encoding=""). * ...
- USB printer: output file creation failure now causes a disconnect - re-implemented "options" parameter for additional options of connected devices (currently only used to set the speed reported ...