当前位置:网站首页>leetcode刷题:二叉树21(验证二叉搜索树)
leetcode刷题:二叉树21(验证二叉搜索树)
2022-07-07 10:30:00 【涛涛英语学不进去】
98.验证二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
把二叉树中序遍历,再把结果集遍历,如果结果集为升序,则是二叉搜索树,因为二叉搜索树的性质为 中序遍历是非递减的。本题提示 要求递增,所以不会出现相等的情况。
package com.programmercarl.tree;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/** * @ClassName IsValidBST * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 21:32 * @Version 1.0 * https://leetcode.cn/problems/validate-binary-search-tree/ * 98. 验证二叉搜索树 **/
public class IsValidBST {
/** * 直接中序遍历获取结果 * 如果结果遍历后是 递增,则验证成功 * * @param root * @return */
public boolean isValidBST(TreeNode root) {
if (root.left == null && root.right == null) {
return true;
}
Deque<Integer> deque = new ArrayDeque<Integer>();
inorderTraversal(root, deque);
Integer pre = deque.poll();
Integer last = null;
//前一个值和后一个值比较,如果不是升序,则不是二叉搜索树
while (!deque.isEmpty()) {
last = deque.poll();
if (pre >= last) {
return false;
} else {
pre = last;
}
}
return true;
}
public void inorderTraversal(TreeNode root, Deque<Integer> deque) {
if (root == null) {
return;
}
//中序遍历 左 中 右
inorderTraversal(root.left, deque);
deque.offer(root.val);
inorderTraversal(root.right, deque);
}
}
边栏推荐
- 解决 Server returns invalid timezone. Go to ‘Advanced’ tab and set ‘serverTimezone’ property manually
- Will the filing free server affect the ranking and weight of the website?
- 【统计学习方法】学习笔记——第五章:决策树
- OSPF exercise Report
- BGP actual network configuration
- Upgrade from a tool to a solution, and the new site with praise points to new value
- (to be deleted later) yyds, paid academic resources, please keep a low profile!
- An error occurred when vscade tried to create a file in the target directory: access denied [resolved]
- 什么是局域网域名?如何解析?
- Airserver automatically receives multi screen projection or cross device projection
猜你喜欢
EPP+DIS学习之路(1)——Hello world!
Sort out the garbage collection of JVM, and don't involve high-quality things such as performance tuning for the time being
Hi3516 full system type burning tutorial
OSPF exercise Report
The hoisting of the upper cylinder of the steel containment of the world's first reactor "linglong-1" reactor building was successful
Pule frog small 5D movie equipment | 5D movie dynamic movie experience hall | VR scenic area cinema equipment
The left-hand side of an assignment expression may not be an optional property access.ts(2779)
金融数据获取(三)当爬虫遇上要鼠标滚轮滚动才会刷新数据的网页(保姆级教程)
<No. 9> 1805. 字符串中不同整数的数目 (简单)
关于 Web Content-Security-Policy Directive 通过 meta 元素指定的一些测试用例
随机推荐
【统计学习方法】学习笔记——支持向量机(下)
When OSPF specifies that the connection type is P2P, it enables devices on both ends that are not in the same subnet to Ping each other
2022 年第八届“认证杯”中国高校风险管理与控制能力挑战赛
<No. 8> 1816. Truncate sentences (simple)
Up meta - Web3.0 world innovative meta universe financial agreement
About sqli lab less-15 using or instead of and parsing
Tutorial on principles and applications of database system (010) -- exercises of conceptual model and data model
<No. 9> 1805. 字符串中不同整数的数目 (简单)
顶级域名有哪些?是如何分类的?
SQL lab 1~10 summary (subsequent continuous update)
Preorder, inorder and postorder traversal of binary tree
利用棧來實現二進制轉化為十進制
浅谈估值模型 (二): PE指标II——PE Band
On valuation model (II): PE index II - PE band
(待会删)yyds,付费搞来的学术资源,请低调使用!
BGP actual network configuration
Niuke website
idm服务器响应显示您没有权限下载解决教程
Airserver automatically receives multi screen projection or cross device projection
Typescript interface inheritance