第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0098. 验证二叉搜索树
题目地址(98. 验证二叉搜索树)
题目描述
1
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
2
3
假设一个二叉搜索树具有如下特征：
4
5
节点的左子树只包含小于当前节点的数。
6
节点的右子树只包含大于当前节点的数。
7
所有左子树和右子树自身必须也是二叉搜索树。
8
示例 1:
9
10
输入:
11
2
12
/ \
13
1 3
14
输出: true
15
示例 2:
16
17
输入:
18
5
19
/ \
20
1 4
21
/ \
22
3 6
23
输出: false
24
解释: 输入为: [5,1,4,null,null,3,6]。
25
根节点的值为 5 ，但是其右子节点值为 4 。
Copied!
前置知识
- 中序遍历
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
中序遍历
这道题是让你验证一棵树是否为二叉查找树（BST）。 由于中序遍历的性质
如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST), 我们只需要中序遍历，然后两两判断是否有逆序的元素对即可，如果有，则不是 BST，否则即为一个 BST。定义法
根据定义，一个结点若是在根的左子树上，那它应该小于根结点的值而大于左子树最小值；若是在根的右子树上，那它应该大于根结点的值而小于右子树最大值。也就是说，每一个结点必须落在某个取值范围：
- 1.根结点的取值范围为（考虑某个结点为最大或最小整数的情况）：(long_min, long_max)
- 2.左子树的取值范围为：(current_min, root.value)
- 3.右子树的取值范围为：(root.value, current_max)
关键点解析
- 二叉树的基本操作（遍历）
- 中序遍历一个二叉查找树（BST）的结果是一个有序数组
- 如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST)
代码
中序遍历
- 语言支持：JS，C++, Java
JavaScript Code：
1
/*
2
* @lc app=leetcode id=98 lang=javascript
3
*
4
* [98] Validate Binary Search Tree
5
*/
6
/**
7
* Definition for a binary tree node.
8
* function TreeNode(val) {
9
* this.val = val;
10
* this.left = this.right = null;
11
* }
12
*/
13
/**
14
* @param {TreeNode} root
15
* @return {boolean}
16
*/
17
var isValidBST = function (root) {
18
if (root === null) return true;
19
if (root.left === null && root.right === null) return true;
20
const stack = [root];
21
let cur = root;
22
let pre = null;
23
24
function insertAllLefts(cur) {
25
while (cur && cur.left) {
26
const l = cur.left;
27
stack.push(l);
28
cur = l;
29
}
30
}
31
insertAllLefts(cur);
32
33
while ((cur = stack.pop())) {
34
if (pre && cur.val <= pre.val) return false;
35
const r = cur.right;
36
37
if (r) {
38
stack.push(r);
39
insertAllLefts(r);
40
}
41
pre = cur;
42
}
43
44
return true;
45
};
Copied!
C++ Code：
1
// 递归
2
class Solution {
3
public:
4
bool isValidBST(TreeNode* root) {
5
TreeNode* prev = nullptr;
6
return validateBstInorder(root, prev);
7
}
8
9
private:
10
bool validateBstInorder(TreeNode* root, TreeNode*& prev) {
11
if (root == nullptr) return true;
12
if (!validateBstInorder(root->left, prev)) return false;
13
if (prev != nullptr && prev->val >= root->val) return false;
14
prev = root;
15
return validateBstInorder(root->right, prev);
16
}
17
};
18
19
// 迭代
20
class Solution {
21
public:
22
bool isValidBST(TreeNode* root) {
23
auto s = vector<TreeNode*>();
24
TreeNode* prev = nullptr;
25
while (root != nullptr || !s.empty()) {
26
while (root != nullptr) {
27
s.push_back(root);
28
root = root->left;
29
}
30
root = s.back();
31
s.pop_back();
32
if (prev != nullptr && prev->val >= root->val) return false;
33
prev = root;
34
root = root->right;
35
}
36
return true;
37
}
38
};
Copied!
Java Code:
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public boolean isValidBST(TreeNode root) {
12
Stack<Integer> stack = new Stack<> ();
13
TreeNode previous = null;
14
15
while (root != null || !stack.isEmpty()) {
16
while (root != null) {
17
stack.push(root);
18
root = root.left;
19
}
20
root = stack.pop();
21
if (previous != null && root.val <= previous.val ) return false;
22
previous = root;
23
root = root.right;
24
}
25
return true;
26
}
27
}
Copied!
定义法
- 语言支持：C++，Python3, Java, JS
C++ Code：
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
// 递归
11
class Solution {
12
public:
13
bool isValidBST(TreeNode* root) {
14
return helper(root, LONG_MIN, LONG_MAX);
15
}
16
private:
17
bool helper(const TreeNode* root, long min, long max) {
18
if (root == nullptr) return true;
19
if (root->val >= max || root->val <= min) return false;
20
return helper(root->left, min, root->val) && helper(root->right, root->val, max);
21
}
22
};
23
24
// 循环
25
class Solution {
26
public:
27
bool isValidBST(TreeNode* root) {
28
if (root == nullptr) return true;
29
auto ranges = queue<pair<long, long>>();
30
ranges.push(make_pair(LONG_MIN, LONG_MAX));
31
auto nodes = queue<const TreeNode*>();
32
nodes.push(root);
33
while (!nodes.empty()) {
34
auto sz = nodes.size();
35
for (auto i = 0; i < sz; ++i) {
36
auto range = ranges.front();
37
ranges.pop();
38
auto n = nodes.front();
39
nodes.pop();
40
if (n->val >= range.second || n->val <= range.first) {
41
return false;
42
}
43
if (n->left != nullptr) {
44
ranges.push(make_pair(range.first, n->val));
45
nodes.push(n->left);
46
}
47
if (n->right != nullptr) {
48
ranges.push(make_pair(n->val, range.second));
49
nodes.push(n->right);
50
}
51
}
52
}
53
return true;
54
}
55
};
Copied!
Python Code:
1
# Definition for a binary tree node.
2
# class TreeNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.left = None
6
# self.right = None
7
8
class Solution:
9
def isValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) -> bool:
10
"""思路如上面的分析，用Python表达会非常直白
11
:param root TreeNode 节点
12
:param area tuple 取值区间
13
"""
14
if root is None:
15
return True
16
17
is_valid_left = root.left is None or\
18
(root.left.val < root.val and area[0] < root.left.val < area[1])
19
is_valid_right = root.right is None or\
20
(root.right.val > root.val and area[0] < root.right.val < area[1])
21
22
# 左右节点都符合，说明本节点符合要求
23
is_valid = is_valid_left and is_valid_right
24
25
# 递归下去
26
return is_valid\
27
and self.isValidBST(root.left, (area[0], root.val))\
28
and self.isValidBST(root.right, (root.val, area[1]))
Copied!
Java Code:
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public boolean isValidBST(TreeNode root) {
12
return helper(root, null, null);
13
}
14
15
private boolean helper(TreeNode root, Integer lower, Integer higher) {
16
if (root == null) return true;
17
18
if (lower != null && root.val <= lower) return false;
19
if (higher != null && root.val >= higher) return false;
20
21
if (!helper(root.left, lower, root.val)) return false;
22
if (!helper(root.right, root.val, higher)) return false;
23
24
return true;
25
}
26
}
Copied!
JavaScript Code:
1
/**
2
* Definition for a binary tree node.
3
* function TreeNode(val) {
4
* this.val = val;
5
* this.left = this.right = null;
6
* }
7
*/
8
/**
9
* @param {TreeNode} root
10
* @return {boolean}
11
*/
12
var isValidBST = function (root) {
13
if (!root) return true;
14
return valid(root);
15
};
16
17
function valid(root, min = -Infinity, max = Infinity) {
18
if (!root) return true;
19
const val = root.val;
20
if (val <= min) return false;
21
if (val >= max) return false;
22
return valid(root.left, min, val) && valid(root.right, val, max);
23
}
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
相关题目
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
最近更新 1yr ago