新博文地址:[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.
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.
判断二叉搜索,这道题有个坑,首先我们要理解清楚二叉搜索树的概念:
二叉搜索树(BST)
二叉搜索树(也叫二叉排序树)或者是空树,或者满足一下三个条件:
1. 如果左子树不空,则左子树所有关键字都小于根关键字值
2. 如果右子树不空,则右子树所有关键字都大于根关键字值
3. 左右子树又各是一颗二叉搜索树
1. 如果左子树不空,则左子树所有关键字都小于根关键字值
2. 如果右子树不空,则右子树所有关键字都大于根关键字值
3. 左右子树又各是一颗二叉搜索树
下面来看这样的定义:
或者是空树,或者满足这样的条件:
1. 左子树值 < 根值
2. 右子树值 > 根植
3. 左右子树各是二叉排序树
1. 左子树值 < 根值
2. 右子树值 > 根植
3. 左右子树各是二叉排序树
这样的定义对吗?跟上面的BST的定义有什么区别呢?
首先:答案是肯定有区别的,来看这样一棵树
5
/ \
4 10
/ \
3 11
/ \
4 10
/ \
3 11
它肯定不是BST,但是满足下面的定义,因此,要注意在证明BST的时候,不应该只和父节点作比较
事实上,BST的中序遍历是一个递增数列,我们可以根据这一个特性来判断BST的合法性。
中序遍历是很容易的,判断一个list是否是递增也是很容易的。代码如下:
List<Integer> list = new ArrayList<Integer>(); public boolean isValidBST(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return true; } inorderTraversal(root); for(int i = 1; i < list.size();i++){ if(list.get(i) <= list.get(i - 1)){ return false; } } return true; } public void inorderTraversal(TreeNode root){ if(root == null){ return; } inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); }
不过中序遍历判断法实用了O(n)的空间。
还可以直接实用递归来判断BST的合法性:
用到的技巧是:
1. 左子树具有和父节点一样的下限
2. 右子树具有和父节点一样的上限
3. 左(右)子树的上(下)限是父节点
2. 右子树具有和父节点一样的上限
3. 左(右)子树的上(下)限是父节点
代码如下:
public boolean isValidBST(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return true; } return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isValid(TreeNode root, int min, int max) { if(root == null){ return true; } if (root.val >= max || root.val <= min) { return false; } return isValid(root.left, min,root.val) && isValid(root.right, root.val, max); }
相关推荐
LeetCode-BinarySearch
leetcode-tag-Tree
leetcode卡leetcode 二叉树卡片 LeetCode 二叉树卡片问题的章节智解
作者: 负雪明烛个人博客: :
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
最大公共字符串leetcode 二叉树 二叉树是一种抽象的数据结构,由根节点和左右子树组成。 一个节点可以有零个、一个或两个子节点。 二叉树的类型 目标 能够熟悉二叉树上的各种术语。 能够实现二叉树节点。 能够使用...
leetcode卡除非您已经使用过卡片,否则不要看这里。 做真实的自己!
leetcode的题目:Balanced Binary Tree
Pow(xn) leetcode Binary-Search-3 问题1 Pow(x,n) () 问题2 找到 K 个最近的元素 ()
Binary-Search-1 问题1 搜索二维矩阵() 问题1 在旋转排序数组中搜索 () 问题2 在无限排序数组中搜索: 给定一个未知长度的排序数组和一个要搜索的数字,返回该数字在数组中的索引。 越界访问元素会引发异常。 如果该...
leetcode110 二叉树_高度平衡 力扣110
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 ...
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...
Programming Questions on BinarySearch, LeetCode, CodeChef
* [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卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
704.Binary_Search二分查找【LeetCode单题讲解系列】
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
leetcode 2 二叉树打印机 在极小的区域打印二叉树。...>binary-tree-printer</ artifactId > < version >1.0.0</ version > </ dependency > 例子 打印随机 BST。 BTPrinter . printRandom
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】