`
844604778
  • 浏览: 544903 次
文章分类
社区版块
存档分类
最新评论

[互联网面试笔试汇总C/C++-16] 判断一棵二叉树是否是平衡二叉树

 
阅读更多

首先,看一下平衡二叉树的定义:

平衡二叉树(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++笔试题(附答案,华为面试题系列)

    C++提供了一个C 连接交换指定符号extern“C”来解决这个问题。 (4). switch()中不允许的数据类型是? 答:实型 4. 回答下面的问题(6分) (1).Void GetMemory(char **p, int num){ *p = (char *)malloc(num); } void ...

    C/C++常见细节性笔试题

    如array(数组), tree(二叉树)等 另外包含一些常见C/C++考题的验证性实现,如Util,virtual 其中以Util.cpp, Virtual.cpp最有价值, Util包含一些细节性的笔试题目; Virtual则包含常见和虚函数相关...

    c++栈,堆,二叉树代码

    c++数据结构栈,队列,二叉树的代码实现;为了找工作面试笔试而准备的

    vcmianshi.rar_c++ thread_算法笔试面试_算法面试题_马戏团

    C++程序员面试、笔试经常遇到的一些算法示例集 pdf,相关内容:字符串匹配的KMP算法,括号匹配检测、求一个数组的最长递减字序列、一些数字题求解,输出一个字符串的所有组合,马戏团表演问题、Thread.sleep 与obj....

    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...

    免费下载:C语言难点分析整理.doc

    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++基本程序题(尤其适合嵌入式软件岗位的同学),几乎囊括了链表堆栈队列二叉树字符串排序所有基本程序,可直接打印成小抄,楼主自从有了这个基本上笔试必...

    史上最强的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...

    高级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...

    高级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...

    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...

    高级进阶c语言教程..doc

    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语言难点分析整理.doc

    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 的返回值...

    安芯网盾笔试题目

    凭记忆写下的笔试题目和答案,大概是内存、数据结构、二叉树、排序等等

    C++数据结构各大公司笔试面试题

    ACM程序设计导引及在线实践;...程序员代码面试指南-第三章二叉树[牛客试网试读版];程序员代码面试指南-第四章递归和动态规划[牛客试网试读版];软件技术基础:离散数学、数据结构、C.编程实训 .来可伟.文字版

    富士通部分笔试2013

    参加富士通笔试总结 富士通笔试 选择: 1、二叉树遍历、平衡二叉树(感觉这是全国计算机二级的内容) 2、计算机通信网络ISO七层模型、UDP等 3、数据结构的内容 4、C/C++的内容 5、其他的忘了

    C++及数据结构复习笔记

    本文章适合C++初学者的快速复习和应届生的笔试面试准备,书中给出了大量的面试题,以帮助读者快速的掌握C++的基本概念。对于初学者来说,也可以加强对C++的认识。 文档主要分为C++基本知识,C++数据结构2个部分。...

    2022 Baidu 百度 后端-研发B卷笔试题

    C++代码分析,seq指令,最小生成树,二叉树,数据链路层,代码找错、js文件、树的双亲,内联函数,php脚本,时间复杂度,像素编程,序列反转编程,

    初级java笔试题-BSc-University-Coursework::desktop_computer:我大学期间所有课程项目的集合

    初级java笔试题 BSc 大学课程 “这是我在大学期间的课程作业集” 文件: 高级游戏编程。 高级游戏编程模块教授 C++、图形、网络和多线程方面的高级编程概念。 它完全通过实践课程进行评估,让学生可以自由探索他们感...

    2022年BIGO 开发工程师(基础架构)笔试题

    int **,for执行次数,颠簸,web服务器,cookie,session,类,二进制数,IPV6,完全二叉树,判断两棵树是否相等,8*8棋盘

Global site tag (gtag.js) - Google Analytics