leecode 树是否是平衡树 java
2024-08-26 11:49:46
https://oj.leetcode.com/problems/validate-binary-search-tree/
1.中序遍历是否有序
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int a=-(1<<31); public boolean isValidBST(TreeNode root) { return middle(root); }
public boolean middle(TreeNode root)
{
if(root==null) return true;
if(!middle(root.left)) return false;
if(root.val<=a)
{
return false; } a=root.val;
return middle(root.right); }
}
2.记住每个节点的范围 开始时候(min,max)设为int最大,最小,然后在左子树上范围为(min, root.val) 判断节点是否在范围;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) { int min=-(1<<31);
int max=1<<31-1;
return isValid(root,min,max); }
public boolean isValid(TreeNode root,int min,int max)
{
if(root==null) return true;
if(root.val>min&&root.val<max)
{
return isValid(root.left,min,root.val)&&isValid(root.right,root.val,max); }
return false; }
}
最新文章
- 【转】Unix NetWork Programming——环境搭建(解决unp.h等源码编译问题)
- C++ Pitfalls 之 reference to an object in a dynamically allocated containter
- WinForm------GridControl右键添加动态菜单
- zoj 3644(dp + 记忆化搜索)
- Android – 学习操作NFC – 2
- C#和Javascript间互转的Xxtea加解密
- jQuery预加载插件
- attitude
- 宏中";#";和";##";的用法
- prototype constructor __proto__
- 基于visual Studio2013解决C语言竞赛题之1045打印成绩
- Java Maps
- cordova 自定义 plugin
- platform模块
- Linux大页内存管理等---菜鸟初学
- 【并发】1、关于线程的几种状态&;关于yield的理解
- 【Spring学习笔记-2】Myeclipse下第一个Spring程序-通过ClassPathXmlApplicationContext加载配置文件
- Linux修改本地时间
- WinPE作为启动硬盘
- Linux下的shell编程入门