LeetCode 0098 - Validate Binary Search Tree
# Hints
DFS
中序遍历
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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.
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
The number of nodes in the tree is in the range .
# 题意
给定一棵二叉树,判断其是否为二叉查找树。
# 题解
思路 1 :
考虑二叉查找树的基本性质,对于树上任意一个节点,其键值一定大于左子树的最大值、小于右子树的最小值。那么我们可以直接 DFS 求出每个子树上的最大值和最小值,然后检查是否满足条件即可。
另一种实现方式是在 DFS 时维护当前节点的合法值域,本质上是相同的,但代码更简洁巧妙,见 AC 代码(2)。
思路 2 :
二叉查找树的中序遍历序列是一个严格递增序列,那么我们可以直接中序遍历,然后检查当前节点的值是否比上一个访问的节点的值更大即可。
细节问题:
- 注意值域为
[INT_MIN, INT_MAX]
,在某些代码实现中,需使用long long
类型或是额外的标记变量来维护 DFS 的初始值。
# AC代码(1)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode * left;
* TreeNode * right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode * left, TreeNode * right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int MAX = INT_MAX;
int MIN = INT_MIN;
public:
bool isValidBST(TreeNode * root) {
// DFS
int vmax = MIN, vmin = MAX;
return dfs(root, vmax, vmin);
}
// 深度优先搜索
bool dfs(TreeNode * p, int & f_vmax, int & f_vmin) {
// 递归左子树
if (p->left != nullptr) {
int vmax = MIN, vmin = MAX;
if (!dfs(p->left, vmax, vmin) || p->val <= vmax) {
return false;
}
f_vmax = max(f_vmax, vmax);
f_vmin = min(f_vmin, vmin);
}
// 递归右子树
if (p->right != nullptr) {
int vmax = MIN, vmin = MAX;
if (!dfs(p->right, vmax, vmin) || p->val >= vmin) {
return false;
}
f_vmax = max(f_vmax, vmax);
f_vmin = min(f_vmin, vmin);
}
// 返回
f_vmax = max(f_vmax, p->val);
f_vmin = min(f_vmin, p->val);
return true;
}
};
# AC代码(2)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode * left;
* TreeNode * right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode * left, TreeNode * right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int MAX = INT_MAX;
int MIN = INT_MIN;
public:
bool isValidBST(TreeNode * root) {
// DFS
return dfs(root, MIN, MAX, false, false);
}
// 深度优先搜索
bool dfs(TreeNode * p, int vmin, int vmax, bool flagmin, bool flagmax) {
// 递归终止
if ((flagmin && p->val <= vmin) || (flagmax && p->val >= vmax)) {
return false;
}
// 递归
if (p->left != nullptr && !dfs(p->left, vmin, p->val, flagmin, true)) {
return false;
}
if (p->right != nullptr && !dfs(p->right, p->val, vmax, true, flagmax)) {
return false;
}
// 返回
return true;
}
};
# AC代码(3)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode * left;
* TreeNode * right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode * left, TreeNode * right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode * root) {
// DFS
TreeNode * prv = nullptr;
return dfs(root, prv);
}
// 深度优先搜索:中序遍历
bool dfs(TreeNode * p, TreeNode * & prv) {
// 递归左子树
if (p->left != nullptr && !dfs(p->left, prv)) {
return false;
}
// 更新答案
if (prv != nullptr && p->val <= prv->val) {
return false;
}
prv = p;
// 递归右子树
if (p->right != nullptr && !dfs(p->right, prv)) {
return false;
}
// 返回
return true;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01