当前位置:网站首页>Leetcode problem solving -- 98 Validate binary search tree
Leetcode problem solving -- 98 Validate binary search tree
2022-07-06 03:07:00 【Snowy solitary boat】
Recursive version
public boolean isValidBST(TreeNode root) {
return range(root,Integer.MIN_VALUE-1L,Integer.MAX_VALUE+1L);
}
public boolean range(TreeNode node,long min,long max){
if (node==null) return true;
if (node.val<=min||node.val>=max) return false;
return range(node.left,min,node.val)&&range(node.right,node.val,max);
}
Wrong thinking :
Before saying the right way of thinking , Let me first talk about the pit I stepped on , I was thinking about recursion , Then judge whether the value of the left node is greater than or equal to the root node or the value of the right node is less than or equal to the root node , Just go back to false, But in fact, this is not possible , Please look at the chart below.
7 / \ 2 5 / \ 1 9
According to the above idea, the result is true, This is because the upper limit of the left subtree is ignored , And the right subtree has the error caused by the lower limit
The right way of thinking :
Use the upper and lower limits to judge
- Because the root node has no upper and lower limits , Therefore, the maximum and minimum values that can be stored by the variable type are used as the upper and lower limits
- If the node is null Go straight back to true
- If the node is not null, And the node value is not within the range specified by the upper and lower limits ,return false
- Continue to judge subtree , But should pay attention to , The upper limit of the left subtree is the value of the current subtree , The lower limit of the right subtree is the value of the current subtree
Iteration version
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
long prev = Integer.MIN_VALUE-1L;
while (!stack.isEmpty()||node!=null){
while (node!=null){
stack.push(node);
node = node.left;
}
node = stack.pop();
if (node.val<=prev) return false;
prev = node.val;
node = node.right;
}
return true;
}
Ideas :
BSTree In the middle order traversal of , The value of the previous node to be traversed must be less than the value of the next node to be traversed , Therefore, a node that stores the value of the previous traversed node is added prev Variables for comparison
This scheme is based on the understanding of the iterative method of middle order traversal , If a little partner doesn't know , And I want to know more about the explanation idea of middle order traversal iteration , Sure Click here to jump
边栏推荐
- [network security interview question] - how to penetrate the test file directory through
- 深入探究指针及指针类型
- Technology sharing | what if Undo is too big
- XSS challenges绕过防护策略进行 XSS 注入
- Derivation of anti Park transform and anti Clarke transform formulas for motor control
- 如何做好功能测试
- Yyds dry inventory comparison of several database storage engines
- 纯Qt版中国象棋:实现双人对战、人机对战及网络对战
- BUUCTF刷题笔记——[极客大挑战 2019]EasySQL 1
- Installation and use tutorial of cobaltstrike-4.4-k8 modified version
猜你喜欢
codeforces每日5題(均1700)-第六天
【概念】Web 基础概念认知
Is there a completely independent localization database technology
Apt installation ZABBIX
RobotFramework入门(一)简要介绍及使用
【 kubernets series】 a Literature Study on the Safe exposure Applications of kubernets Service
Era5 reanalysis data download strategy
Modeling specifications: naming conventions
[Chongqing Guangdong education] higher mathematics I reference materials of Southwest Petroleum University
C # create self host webservice
随机推荐
Solve 9 with C language × 9 Sudoku (personal test available) (thinking analysis)
【Unity3D】GUI控件
1. Dynamic parameters of function: *args, **kwargs
MySQL advanced notes
XSS challenges绕过防护策略进行 XSS 注入
Master data management theory and Practice
OCR文字识别方法综述
Single instance mode of encapsulating PDO with PHP in spare time
Analyze 菜单分析
Polymorphic day02
MySQL advanced notes
Sign SSL certificate as Ca
Redis SDS principle
[matlab] access of variables and files
QT release exe software and modify exe application icon
jsscript
Which ecology is better, such as Mi family, graffiti, hilink, zhiting, etc? Analysis of five mainstream smart brands
Spherical lens and cylindrical lens
Prototype design
C language - Blue Bridge Cup - promised score