首先,看一下平衡二叉树的定义:
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
思路:利用递归的思想
代码:
int DepthTree(BSTreeNode *pbs)
{
if (pbs==NULL)
return 0;
else
{
int leftLength=DepthTree(pbs->left);
int rigthLength=DepthTree(pbs->right);
return 1+(leftLength>rigthLength ? leftLength:rigthLength);
}
}
bool isBalanceTree(BSTreeNode *pbs)
{
if (pbs==NULL)
{
return true;
}
int depthLeft=DepthTree(pbs->left);
int depthRight=DepthTree(pbs->right);
if (abs(depthLeft-depthRight)>1)
return false;
else
return isBalanceTree(pbs->left) && isBalanceTree(pbs->right);
}
改进:这样实际上是有很多重复计算的,如果想进一步提高效率的话则需要考虑如何每个结点只遍历一次。
其实就是一边遍历一遍进行判断。
代码:
bool isBalanceTree(Node* pRoot, int * pDepth)
{
if(pRoot==NULL)
{
*pDepth = 0;
return true;
}
int right,left;
if(isBalanceTree(pRoot->left,&left)&&isBalanceTree(pRoot->right,&right))
{
if(left-right < 1 && right-left < 1)
{
pDepth = 1 + (left>right)?left:right;
return true;
}
}
return false;
}
方法一和方法二,一个是从上往下进行判断,一个是从下往上进行判断,一个有很多重复,一个没有重复,读者可以自己体会。
分享到:
相关推荐
C++提供了一个C 连接交换指定符号extern“C”来解决这个问题。 (4). switch()中不允许的数据类型是? 答:实型 4. 回答下面的问题(6分) (1).Void GetMemory(char **p, int num){ *p = (char *)malloc(num); } void ...
如array(数组), tree(二叉树)等 另外包含一些常见C/C++考题的验证性实现,如Util,virtual 其中以Util.cpp, Virtual.cpp最有价值, Util包含一些细节性的笔试题目; Virtual则包含常见和虚函数相关...
c++数据结构栈,队列,二叉树的代码实现;为了找工作面试笔试而准备的
C++程序员面试、笔试经常遇到的一些算法示例集 pdf,相关内容:字符串匹配的KMP算法,括号匹配检测、求一个数组的最长递减字序列、一些数字题求解,输出一个字符串的所有组合,马戏团表演问题、Thread.sleep 与obj....
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
根据我两个半月找工作笔试面试经验吐血整理好的最常考的C/C++基本程序题(尤其适合嵌入式软件岗位的同学),几乎囊括了链表堆栈队列二叉树字符串排序所有基本程序,可直接打印成小抄,楼主自从有了这个基本上笔试必...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值 383...
67. C/C++ 误区一:void main() 373 68. C/C++ 误区二:fflush(stdin) 376 69. C/C++ 误区三:强制转换 malloc() 的返回值 380 70. C/C++ 误区四:char c = getchar(); 381 71. C/C++ 误区五:检查 new 的返回值...
凭记忆写下的笔试题目和答案,大概是内存、数据结构、二叉树、排序等等
ACM程序设计导引及在线实践;...程序员代码面试指南-第三章二叉树[牛客试网试读版];程序员代码面试指南-第四章递归和动态规划[牛客试网试读版];软件技术基础:离散数学、数据结构、C.编程实训 .来可伟.文字版
参加富士通笔试总结 富士通笔试 选择: 1、二叉树遍历、平衡二叉树(感觉这是全国计算机二级的内容) 2、计算机通信网络ISO七层模型、UDP等 3、数据结构的内容 4、C/C++的内容 5、其他的忘了
本文章适合C++初学者的快速复习和应届生的笔试面试准备,书中给出了大量的面试题,以帮助读者快速的掌握C++的基本概念。对于初学者来说,也可以加强对C++的认识。 文档主要分为C++基本知识,C++数据结构2个部分。...
C++代码分析,seq指令,最小生成树,二叉树,数据链路层,代码找错、js文件、树的双亲,内联函数,php脚本,时间复杂度,像素编程,序列反转编程,
初级java笔试题 BSc 大学课程 “这是我在大学期间的课程作业集” 文件: 高级游戏编程。 高级游戏编程模块教授 C++、图形、网络和多线程方面的高级编程概念。 它完全通过实践课程进行评估,让学生可以自由探索他们感...
int **,for执行次数,颠簸,web服务器,cookie,session,类,二进制数,IPV6,完全二叉树,判断两棵树是否相等,8*8棋盘