Ввод: root = [10,5,11,-2,7,null,15,null,null,4]
Вывод: false
Объяснение: вершина 4 находится в левом поддереве вершины 10, значит 4 должно быть меньше 10 (это верно), так же вершина 4 в правом поддереве вершины 5, значит 4 должно быть больше 5 - а это не так, поэтому вернем false
Ограничения:
Число узлов в дереве >= 1
Высота дерева <= 1000
Значение вершин дерева лежит в диапазоне [-pow(2,31), pow(2,31) - 1] (включительно). Например, pow(2,3) - означает два в третьей степени
/**
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
private static bool IsValid(TreeNode root, long low, long high)
{
if (root == null)
{
return true;
}
// если текущая вершина не удволетворяет условиям BST, то и все дерево
// не является правильным BST и возвращаем false
if (!(low < root.val && root.val < high))
{
return false;
}
// обновляем минимальное и максимальное значение для поддеревьев
return IsValid(root.left, low, root.val) &&
IsValid(root.right, root.val, high);
}
public static bool IsValidBst(TreeNode root)
{
// в качестве начальных значений указываем значение, которое
// меньше самого минимального значения в дереве и больше самого максимального
// (см. ограничения)
return IsValid(root, long.MinValue, long.MaxValue);
}
}
#include <vector>
using namespace std;
/**
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
bool isValid(TreeNode* root, int64_t low, int64_t high) {
if (root == nullptr) {
return true;
}
// если текущая вершина не удволетворяет условиям BST, то и все дерево
// не является правильным BST и возвращаем false
if (!(low < root->val && root->val < high)) {
return false;
}
// обновляем минимальное и максимальное значение для поддеревьев
return isValid(root->left, low, root->val) &&
isValid(root->right, root->val, high);
}
bool isValidBst(TreeNode* root) {
// в качестве начальных значений указываем значение, которое
// меньше самого минимального значения в дереве и больше самого максимального
// (см. ограничения)
return isValid(root, INT64_MIN, INT64_MAX);
}
package main
import "math"
/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValid(node *TreeNode, low, high int64) bool {
if node == nil {
return true
}
nodeValue := int64(node.Val)
// если текущая вершина не удволетворяет условиям BST, то и все дерево
// не является правильным BST и возвращаем false
if !(low < nodeValue && nodeValue < high) {
return false;
}
// обновляем минимальное и максимальное значение для поддеревьев
return isValid(node.Left, low, nodeValue) &&
isValid(node.Right, nodeValue, high)
}
func isValidBst(root *TreeNode) bool {
// в качестве начальных значений указываем значение, которое
// меньше самого минимального значения в дереве и больше самого максимального
// (см. ограничения)
return isValid(root, math.MinInt64, math.MaxInt64)
}
import java.util.*;
/**
* class TreeNode {
* Integer val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(Integer val) { this.val = val; }
* TreeNode(Integer val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean isValid(TreeNode node, long low, long high) {
if (node == null) {
return true;
}
// если текущая вершина не удволетворяет условиям BST, то и все дерево
// не является правильным BST и возвращаем false
if (!(low < node.val && node.val < high)) {
return false;
}
// обновляем минимальное и максимальное значение для поддеревьев
return isValid(node.left, low, node.val) &&
isValid(node.right, node.val, high);
}
public boolean isValidBst(TreeNode root) {
// в качестве начальных значений указываем значение, которое
// меньше самого минимального значения в дереве и больше самого максимального
// (см. ограничения)
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def is_valid_bst(root: TreeNode) -> bool:
def is_valid(node: TreeNode, low: int, high: int) -> bool:
if node is None:
return True
# если текущая вершина не удволетворяет условиям BST, то и все дерево
# не является правильным BST и возвращаем false
if not(low < node.val < high):
return False
# обновляем минимальное и максимальное значение для поддеревьев
return (is_valid(node.left, low, node.val) and
is_valid(node.right, node.val, high))
# в качестве начальных значений указываем значение, которое
# меньше самого минимального значения в дереве и больше самого максимального
# (см. ограничения)
return is_valid(root, float("-inf"), float("inf"))
import { TreeNode } from './treeNode.js';
/**
* class TreeNode {
* constructor(val, left, right) {
* this.val = val;
* this.left = (left === undefined ? null : left);
* this.right = (right === undefined ? null : right);
* }
* }
*/
/**
* @param {TreeNode} root
* @returns {boolean}
*/
export function isValid(root, low, high) {
if (root === null) {
return true;
}
// если текущая вершина не удволетворяет условиям BST, то и все дерево
// не является правильным BST и возвращаем false
if (!(low < root.val && root.val < high)) {
return false;
}
// обновляем минимальное и максимальное значение для поддеревьев
return isValid(root.left, low, root.val) &&
isValid(root.right, root.val, high);
}
/**
* @param {TreeNode|null} root
* @returns {boolean}
*/
export function isValidBst(root) {
// в качестве начальных значений указываем значение, которое
// меньше самого минимального значения в дереве и больше самого максимального
// (см. ограничения)
return isValid(root, -Infinity, Infinity);
}
