`
yiyidog125
  • 浏览: 13192 次
  • 性别: Icon_minigender_1
  • 来自: 广州
最近访客 更多访客>>
社区版块
存档分类
最新评论

Verify a binary tree

 
阅读更多
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;
	}

0
1
分享到:
评论

相关推荐

    verify-complete-binary-tree.rar_verify

    在IT领域,排序二叉树是一种特殊的二叉树数据结构,它的每个节点的值都大于其左子树中任意节点的值...通过分析“verify-complete-binary-tree.cpp”的源代码,我们可以深入理解这些概念,并学习如何在实践中应用它们。

    lrucacheleetcode-leetcode:leetcode

    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 ...

    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]...

    a project model for the FreeBSD Project.7z

    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...

    otp-system-documentation

    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 ...

    Git-2.21.0-64-bit.zip

    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=&lt;ref&gt; option. * The code to show args with ...

    Google C++ Style Guide(Google C++编程规范)高清PDF

    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...

    ICS delphixe10源码版

    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 ...

    NativeXml-master

    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=""). * ...

    Bochs - The cross platform IA-32 (x86) emulator

    - 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 ...

Global site tag (gtag.js) - Google Analytics