题目
https://leetcode-cn.com/problems/validate-binary-search-tree/
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
- 如果是一棵空树，也算是有效的二叉搜索树
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
一 错误的思路
遍历二叉树的所有节点，看看所有的节点是否满足
node.left.val < node.val < node.right.val ? 该判断方法存在漏洞
注：这种思路是存在漏洞的
作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！
以下资料在群文件可自行下载！
- 下面是两个反例，虽然每个节点都符合，但是不是一棵二叉搜索树
image
二 思路1 - 中序遍历
-
2.1 二叉搜索树的一个特性：中序遍历（左-root-右），结果必然是升序的。
-
2.2 2.2利用上述特性就可以判断是否为一棵二叉搜索树了
-
核心代码 - 迭代调用
/// 思路一 中序遍历 迭代
- (BOOL)isValidBST:(TreeNode *)root {
if (root == nil) {
return true;
}
Stack *stack = [[Stack alloc] init];
while (true) {
while (root != nil) {
[stack push:root];
root = root.left;
}
if ([stack isEmpty]) {
break;
}
root = [stack pop];
if (self.last != NSNotFound && root.value <= self.last) {
return false;
}
self.last = root.value;
root = root.right;
}
return true;
}
时间复杂度：O(n)，空间复杂度(n)
- 核心代码 - 递归调用
/// 递归调用
- (BOOL)isValidBST2:(TreeNode *)root {
if (root == nil) {
return true;
}
if (![self isValidBST:root.left]) {
return false;
}
if (self.last != NSNotFound && root.value <= self.last) {
return false;
}
self.last = root.value;
if (![self isValidBST:root.right]) {
return false;
}
return true;
}
时间复杂度：O(n)，空间复杂度O(n)
三 思路2 - 遍历的同时指定范围
-
3.1 在遍历每一个节点的时候，都指定它的上界和下界，节点的取值范围是（下界到上界）
-
3.2 这种思想适合所有的遍历方式（前序，中序，后序，层序）
3.1 遍历的同时指定范围 - 前序遍历
// 思路2 - 遍历的同时指定范围 - 前序遍历
- (BOOL)isValidBST3:(TreeNode *)root {
return [self isValidBST3:root min:NSNotFound max:NSNotFound];
}
- (BOOL)isValidBST3:(TreeNode *)node min:(NSInteger)min max:(NSInteger)max {
if (node == nil) {
return true;
}
if (min != NSNotFound && node.value <= min) {
return false;
}
if (max != NSNotFound && node.value >= max ) {
return false;
}
// 遍历左边节点
if (![self isValidBST3:node.left min:min max:node.value]) {
return false;
}
// 遍历右边节点
if (![self isValidBST3:node.right min:node.value max:max]) {
return false;
}
return true;
}
时间复杂度：O(n)，空间复杂度O(n)
3.2 遍历的同时指定范围 - 层序遍历
- 核心代码
/// 思路2 - 遍历的同时指定范围 - 层序遍历
- (BOOL)isValidBST4:(TreeNode *)root {
if (root == nil) {
return true;
}
[self offer:root min:NSNotFound max:NSNotFound];
// 循环遍历
while (!self.nodes.isEmpty) {
TreeNode *node = [self.nodes deQueue];
NSInteger min = [[self.mins objectAtIndex:0] integerValue];
if (min != NSNotFound && node.value <= min) {
return false;
}
NSInteger max = [[self.maxs objectAtIndex:0] integerValue];
if (max != NSNotFound && node.value >= max) {
return false;
}
// 遍历左右子树
[self offer:node.left min:min max:node.value];
[self offer:node.right min:node.value max:max];
}
return true;
}
- (void)offer:(TreeNode *)node min:(NSInteger)min max:(NSInteger)max {
if (node == nil) {
return;
}
[self.nodes enQueue:node];
[self.mins addObject:@(min)];
[self.maxs addObject:@(max)];
}
- 运行结果
2019-11-20 23:14:34.143954+0800 03_CheckIsValidBSTTree[2364:98870] result4 = 1
项目链接地址 - 04_CheckIsValidBSTTree
作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！
推荐阅读
iOS开发——最新 BAT面试题合集（持续更新中）
作者：路飞_Luck
链接：https://www.jianshu.com/p/cfe65c8865c8
来源：简书
网友评论