当前位置:网站首页>Force deduction brush question - 98 Validate binary search tree
Force deduction brush question - 98 Validate binary search tree
2022-07-06 20:17:00 【Java mengxinling】
Daily clock in algorithm problem
subject : Give you the root node of a binary tree root , Determine whether it is an effective binary search tree .
A valid binary search tree is defined as follows :
1. The left subtree of the node contains only Less than Number of current nodes .
2. The right subtree of the node contains only Greater than Number of current nodes .
3. All left and right subtrees themselves must also be binary search trees .
The class definition of the following binary tree is given
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
Their thinking :
First, let's analyze the problem , The subject is very simple , It is to judge whether a given binary tree is a binary search tree .
Binary search tree :
1. For the binary tree, the maximum value of the left subtree of any node is less than the value of the node
2. For any node of the binary tree, the minimum value of the right subtree is greater than the value of the node
3. The left and right subtrees of any node of the binary tree are binary search trees
Set upper and lower bounds :
Every time I recurse to the left , Keep the original minimum value unchanged , Set the value of the current intermediate node to the upper bound
Every time I recurse to the right , Keep the original maximum value unchanged , Set the value of the current intermediate node to the lower bound
Set recursive exit :
Obviously , If the value of the current node does not meet the upper and lower bounds , Then the subtree is not a binary search tree , The root node is not satisfied .
public boolean isValidBST(TreeNode root){
return isValidBST(root,10000000000L,-10000000000L);
}
public boolean isValidBST(TreeNode root,long top,long low) {
if (root.val <= low || root.val >= top){
return false;
}
boolean left = false;
boolean right = false;
if(root.left != null){
left = isValidBST(root.left,root.val,low);
}else {
left = true;
}
if (root.right != null){
right = isValidBST(root.right,top, root.val);
}else {
right = true;
}
if (left && right){
return true;
}else {
return false;
}
}
Pruning optimization :
The code verifies that the binary sort tree must pass through all nodes , If the binary tree is a sort binary tree , Then there is no doubt that all nodes will be verified , But if the tree is not a sorted binary tree , Other recursive paths will continue to be verified , So you can set a global variable outside the method boolean flag = true; Indicates that there are no nodes that are not satisfied , When dissatisfaction occurs, it is set to false, At this time, the initial judgment of the entry method flag, If false Cancel code running directly .
boolean flag = true;
public boolean isValidBST(TreeNode root){
return isValidBST(root,10000000000L,-10000000000L);
}
public boolean isValidBST(TreeNode root,long top,long low) {
if(!flag){
return false;
}
if (root.val <= low || root.val >= top){
return false;
}
boolean left = false;
boolean right = false;
if(root.left != null){
left = isValidBST(root.left,root.val,low);
}else {
left = true;
}
if (root.right != null){
right = isValidBST(root.right,top, root.val);
}else {
right = true;
}
if (left && right){
return true;
}else {
return false;
}
}
边栏推荐
- Leetcode question 283 Move zero
- js获取浏览器系统语言
- Tencent T2 Daniel explained in person and doubled his job hopping salary
- Groovy基础语法整理
- Appx代码签名指南
- 永磁同步电机转子位置估算专题 —— 基波模型与转子位置角
- Wechat applet common collection
- Tencent T3 teaches you hand in hand. It's really delicious
- Jupyter launch didn't respond after Anaconda was installed & the web page was opened and ran without execution
- Tencent T4 architect, Android interview Foundation
猜你喜欢
22-07-05 upload of qiniu cloud storage pictures and user avatars
Tencent Android development interview, basic knowledge of Android Development
22-07-05 七牛云存储图片、用户头像上传
01 basic introduction - concept nouns
An East SMS login resurrection installation and deployment tutorial
5. 無線體內納米網:十大“可行嗎?”問題
腾讯字节等大厂面试真题汇总,网易架构师深入讲解Android开发
beegfs高可用模式探讨
枚举根据参数获取值
夏志刚介绍
随机推荐
Appx代码签名指南
系统与应用监控的思路和方法
JS implementation force deduction 71 question simplified path
Speech recognition (ASR) paper selection: talcs: an open source Mandarin English code switching corps and a speech
Leetcode question 283 Move zero
持续测试(CT)实战经验分享
B-杰哥的树(状压树形dp)
Tencent byte Alibaba Xiaomi jd.com offer got a soft hand, and the teacher said it was great
PowerPivot——DAX(初识)
腾讯安卓开发面试,android开发的基础知识
5. Wireless in vivo nano network: top ten "feasible?" problem
Pay attention to the partners on the recruitment website of fishing! The monitoring system may have set you as "high risk of leaving"
Monthly report of speech synthesis (TTS) and speech recognition (ASR) papers in June 2022
5. 無線體內納米網:十大“可行嗎?”問題
JMeter server resource indicator monitoring (CPU, memory, etc.)
RT thread I2C tutorial
5. Nano - Net in wireless body: Top 10 "is it possible?" Questions
HDU 1026 search pruning problem within the labyrinth of Ignatius and the prince I
8086指令码汇总表(表格)
02 基础入门-数据包拓展