题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
int getHeight(Node node){
if(node==null){
return 0;
}
int heigth = 1;
if(node.left!=null){
height = 1+getHeight(node.left);
}
if(node.rigth!=null){
int h = 1+getHeight(node.right);
height = height>h?height:h;
}
return height;
}
boolean isBalance(Node node){
if(node==null){
return true;
}
int left = getHeight(node.left);
int right = getHeight(node.right);
int diff = left - right;
if(diff > 1 || diff < -1)
return false;
return isBalance(node.left)&&isBalance(node.right);
}
我们用后序遍历的方式遍历二叉树的每一个结点,在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶节点的路径的长度),我们就可以一边遍历一边判断每个结点是不是平衡的
boolean isBalance(Node node,Depth d){
if(node==null){
d.height=0;
return true;
}
Depth right=new Depth();
depth left = new Depth();
if(isBalance(node.left,left)&&isBalance(node.right,right)){
int diff = left.height-right.height;
if(diff<=1||diff>=-1){//绝对值小于等于1
//如果是平衡树,才有必要算深度,然后看上级是不是平衡树
d.height=left.height>right.height?left.height:right.height;
return true
}
}
return false;
}
分享到:
相关推荐
1 数组 3 1.1 求子数组的最大和 3 1.2 查找最小的k个元素 4 1.3 调整数组顺序使奇数位于偶数前面 5 1.4 找出数组中两个只出现一次的数字 5 1.5 旋转数组 7 1.6 旋转数组的最小元素 11 ...2.1 二叉树的非递归操作 15
面试题6:判断程序会出现什么问题 第7章 嵌入式编程 面试题1:编码实现某一变量某位清或置 面试题2:用C编写一个死循环程序 面试题3:用变量a给出下面的定义 面试题4:设置地址为0x67a9的整型变量的值为0xaa66 面试...
程序员面试 100题 前60题 里面的内容主要是 数据结构方面 : 数组 链表 二叉树
1.写出判断ABCD四个表达式的是否正确, 若正确, 写出经过表达式中 a的值(3分) int a = 4; (A)a += (a++); (B) a += (++a) ;(C) (a++) += a;(D) (++a) += (a++); a = ? 答:C错误,左侧不是一个有效变量,不能赋值,可...
道常见的程序员面试题,这些题目偏向中低难度,是入门上手不错的选择。另外这些题目基本上在各大 OJ 上也都有,可以非常方便地提交自己的实现进行练手。 如果刚开始练习算法题目,「剑指 Offer」是个不错的切入点。...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*...84. C语言惠通面试题 428 85. C语言常用宏定义 450
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
不多说了 直接上目录: 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450 有需要的朋友可以根据需求下载,内容为WORD格式的,绝对清晰
高级进阶c语言教程 目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450