#P4060. 验证二叉搜索树
-
ID: 2301
Tried: 78
Accepted: 26
Difficulty: 3
验证二叉搜索树
题目内容
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含 大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
输入描述
一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。
输出描述
输入是是一个有效的二叉搜索树则输出true，否则输出false。
样例1
输入
2 1 3
输出
true
说明
样例2
输入
5 1 4 null null 3 6
输出
false
说明
根节点的值是5 ，但是右子节点的值是 4。
提示
- 树中节点数目范围在[1,104] 内
- −231<=Node.val<=231−1
验证二叉搜索树
思路
-
构造二叉树
根据输入的数组表示构造二叉树：- 输入第一行为节点总数 n
- 第二行为 n 个节点值，空节点用 "null" 表示
- 按照题目描述，节点 i 的左孩子为索引 2i+1，右孩子为索引 2i+2
- 注意：对于 “null” 节点，不创建结点对象
-
判断二叉搜索树（BST）
利用递归上下界方法判断：- 对每个节点，设定允许的取值范围（初始为 (-∞, +∞)）
- 左子树的范围更新为 (min, node.val)；右子树为 (node.val, max)
- 递归遍历所有节点，若某个节点不满足范围条件则返回 false
代码实现
Python 代码
import sys
import math
# 定义二叉树节点
class TreeNode:
__slots__ = ['val', 'left', 'right']
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 根据数组表示构造二叉树
def build_tree(level_order):
if not level_order or level_order[0] == 'null':
return None
root = TreeNode(int(level_order[0]))
queue = [root]
i = 1
while i < len(level_order):
current = queue.pop(0)
# 构造左子节点
if i < len(level_order) and level_order[i] != 'null':
current.left = TreeNode(int(level_order[i]))
queue.append(current.left)
i += 1
# 构造右子节点
if i < len(level_order) and level_order[i] != 'null':
current.right = TreeNode(int(level_order[i]))
queue.append(current.right)
i += 1
return root
# 递归判断 BST，有效范围为 (min_val, max_val)
def is_valid_bst(root, min_val=-math.inf, max_val=math.inf):
if not root:
return True
if not (min_val < root.val < max_val):
return False
return is_valid_bst(root.left, min_val, root.val) and is_valid_bst(root.right, root.val, max_val)
if __name__ == "__main__":
# 读取节点数组（空格分隔）
nodes = sys.stdin.readline().strip().split()
root = build_tree(nodes)
print("true" if is_valid_bst(root) else "false")
C++ 代码
#include <bits/stdc++.h>
using namespace std;
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
if (tokens.empty() || tokens[0] == "null")
return nullptr;
TreeNode* root = new TreeNode(stoi(tokens[0]));
queue<TreeNode*> q;
q.push(root);
int i = 1;
while (i < tokens.size()) {
TreeNode* current = q.front();
q.pop();
// 构造左子节点
if (i < tokens.size() && tokens[i] != "null") {
current->left = new TreeNode(stoi(tokens[i]));
q.push(current->left);
}
i++;
// 构造右子节点
if (i < tokens.size() && tokens[i] != "null") {
current->right = new TreeNode(stoi(tokens[i]));
q.push(current->right);
}
i++;
}
return root;
}
// 递归判断 BST，范围为 (min_val, max_val)
bool isValidBST(TreeNode* root, long min_val = numeric_limits<long>::min(), long max_val = numeric_limits<long>::max()) {
if (!root) return true;
if (!(min_val < root->val && root->val < max_val)) return false;
return isValidBST(root->left, min_val, root->val) && isValidBST(root->right, root->val, max_val);
}
// 释放内存
void freeTree(TreeNode* root) {
if (!root) return;
freeTree(root->left);
freeTree(root->right);
delete root;
}
int main() {
string input;
getline(cin, input);
istringstream iss(input);
vector<string> tokens;
string token;
while (iss >> token) {
tokens.push_back(token);
}
TreeNode* root = buildTree(tokens);
cout << (isValidBST(root) ? "true" : "false") << endl;
freeTree(root);
return 0;
}
Java 代码
import java.util.Scanner;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Main {
// 根据层次遍历构造二叉树
public static TreeNode buildTree(String[] tokens) {
if (tokens.length == 0 || tokens[0].equals("null"))
return null;
TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (i < tokens.length) {
TreeNode current = queue.poll();
// 构造左子节点
if (i < tokens.length && !tokens[i].equals("null")) {
current.left = new TreeNode(Integer.parseInt(tokens[i]));
queue.offer(current.left);
}
i++;
// 构造右子节点
if (i < tokens.length && !tokens[i].equals("null")) {
current.right = new TreeNode(Integer.parseInt(tokens[i]));
queue.offer(current.right);
}
i++;
}
return root;
}
// 递归判断 BST，使用上下界判断方法
public static boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (!(minVal < root.val && root.val < maxVal)) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
String[] nodes = line.split(" ");
TreeNode root = buildTree(nodes);
boolean res = isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
System.out.println(res ? "true" : "false");
sc.close();
}
}