《每周一道算法题》（四）验证二叉搜索树

题目

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

---

每周一道算法题 - 笔记

---