题目
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 ? 该判断方法存在漏洞
注：这种思路是存在漏洞的
- 下面是两个反例，虽然每个节点都符合，但是不是一棵二叉搜索树
image.png
二 思路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
本文参考MJ老师的每周一道算法题，非常感谢
项目链接地址 - 04_CheckIsValidBSTTree
