验证二叉搜索树

思路

1. 构造二叉树
   根据输入的数组表示构造二叉树：

   • 输入第一行为节点总数 n
   • 第二行为 n 个节点值，空节点用 "null" 表示
   • 按照题目描述，节点 i 的左孩子为索引 2i+1，右孩子为索引 2i+2
   • 注意：对于 “null” 节点，不创建结点对象

2. 判断二叉搜索树（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();
    }
}

Leetcode 43.验证二叉搜索树-原题链接

题目内容

给你一个二叉树的根节点 $root$ ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含 大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

输入是是一个有效的二叉搜索树则输出$true$，否则输出$false$。

样例1

输入

2 1 3

输出

true

说明

样例2

输入

5 1 4 null null 3 6

输出

false

说明

根节点的值是$5$ ，但是右子节点的值是 $4$。

提示

• 树中节点数目范围在$[1, 10^4]$ 内
• $-2^{31} <= Node.val <= 2^{31} - 1$