当前位置:网站首页>Recursive method to verify whether a tree is a binary search tree (BST)
Recursive method to verify whether a tree is a binary search tree (BST)
2022-07-07 08:04:00 【Hydrion-Qlz】
98. Verify binary search tree
Medium difficulty 1407
Give you the root node of a binary tree root
, Determine whether it is an effective binary search tree .
It works The binary search tree is defined as follows :
- The left subtree of the node contains only Less than Number of current nodes .
- The right subtree of the node contains only Greater than Number of current nodes .
- All left and right subtrees themselves must also be binary search trees .
Ideas
Verify whether a tree is BST Trees , We must be right about BST The definition of is very clear
- Left subtree All nodes The value of is less than the value of the current node
- Right subtree All nodes The value of is greater than the value of the current node
Therefore, we need to keep the maximum and minimum values from the root node to the current node during recursive traversal
Because the title explains that the value of each node can be taken int All numbers in the range , Then when we specify the minimum value, we can only specify long The minimum value of a type , It could go wrong
So when solving problems, you need to pay attention to the given data range , If the given data range is very large, don't consider the violence law ,99% It's going to be overtime
package cn.edu.xjtu.carlWay.tree.validateBinarySearchTree;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 98. Verify binary search tree * Give you the root node of a binary tree root , Determine whether it is an effective binary search tree . * <p> * It works The binary search tree is defined as follows : * <p> * The left subtree of the node contains only Less than Number of current nodes . * The right subtree of the node contains only Greater than Number of current nodes . * All left and right subtrees themselves must also be binary search trees . * <p> * https://leetcode-cn.com/problems/validate-binary-search-tree/ */
public class Solution {
public boolean isValidBST(TreeNode root) {
return validBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validBST(TreeNode root, long minValue, long maxValue) {
if (root == null) {
return true;
}
if (root.val < maxValue && root.val > minValue) {
return validBST(root.left, minValue, root.val) && validBST(root.right, root.val, maxValue);
}
return false;
}
}
边栏推荐
- C language communication travel card background system
- Leetcode 43 String multiplication (2022.02.12)
- Installing postgresql11 database under centos7
- SQL优化的魅力!从 30248s 到 0.001s
- [unity] several ideas about circular motion of objects
- Linux server development, MySQL cache strategy
- C语言队列
- Leetcode 40: combined sum II
- Few shot Learning & meta learning: small sample learning principle and Siamese network structure (I)
- Info | webrtc M97 update
猜你喜欢
Operation suggestions for today's spot Silver
有 Docker 谁还在自己本地安装 Mysql ?
Explore Cassandra's decentralized distributed architecture
Main window in QT learning 27 application
QT learning 26 integrated example of layout management
【数字IC验证快速入门】10、Verilog RTL设计必会的FIFO
These five fishing artifacts are too hot! Programmer: I know, delete it quickly!
青龙面板-今日头条
LeetCode 90:子集 II
Why should we understand the trend of spot gold?
随机推荐
Content of string
【数字IC验证快速入门】11、Verilog TestBench(VTB)入门
Pytest + allure + Jenkins Environment - - achèvement du remplissage de la fosse
Shell 脚本的替换功能实现
C语言航班订票系统
Most elements
[quick start of Digital IC Verification] 15. Basic syntax of SystemVerilog learning 2 (operators, type conversion, loops, task/function... Including practical exercises)
Implementation of replacement function of shell script
Cnopendata American Golden Globe Award winning data
Leanote private cloud note building
贝叶斯定律
【數字IC驗證快速入門】15、SystemVerilog學習之基本語法2(操作符、類型轉換、循環、Task/Function...內含實踐練習)
2022年茶艺师(中级)考试试题及模拟考试
[UVM practice] Chapter 1: configuring the UVM environment (taking VCs as an example), run through the examples in the book
The element with setfieldsvalue set is obtained as undefined with GetFieldValue
Explore Cassandra's decentralized distributed architecture
微信小程序基本组件使用介绍
【VHDL 并行语句执行】
game攻防世界逆向
Linux server development, redis source code storage principle and data model