检查一个二叉树是否平衡的算法分析与C++实现
2024-08-22 12:33:03
今天面试一个实习生,就想既然是未出校园,那就出一个比较基础的题吧,没想到答的并不如人意,对于树的操作完全不熟悉,因此此题算是未作答。原来我想看一下他分析问题的思路,优化代码的能力。接下来会把最近半年我出的面试题整理出来,以来share给其它同事,而来算是自己校园记忆的一个总结,毕竟自己在项目中已经很久未用到这些知识。其实很多题目都是来源于CareerCup.com。这上面汇集了许多IT名企的面试笔试题目,非常值得找工作的人学习。
言归正传,什么是二叉树是否平衡的定义,如果面试者不知道,那肯定要提出来,而不是简简单单说我对树不熟悉,或者找其他更多更多的理由。
其实可以根据平衡的定义,直接递归访问整棵树,计算子树的高度。
struct TreeNode{
TreeNode *leftChild;
TreeNode *rightChild;
int data;
}; int getHeight(const TreeNode* root){
if( root == nullptr){
return 0;
} return max(getHeight(root->leftChild), getHeight(root->rightChild)) + 1;
} bool isBalanced(const TreeNode* root){
if( root == nullptr){
return true;
} int heightDiff = abs(getHeight(root->leftChild) - getHeight(root->rightChild));
if( heightDiff > 1){
return false;
}
else{
return isBalanced(root->leftChild) && isBalanced(root->rightChild);
}
}
如果开始能给出这个解法那是可以接受的。但是,由于同一个node的高度会被重复计算,因此效率不高。算法复杂度是O(n*logn)。接下来,我们要改进这个算法,使得子树的高度不再重复计算:我们通过删减重复的getHeight(const TreeNode*)调用。其实getHeight不单可以计算子树的高度,其实还可以判断子树是否的平衡的,如果不平衡怎么办?直接返回-1。那该递归调用就可以结束了。
因此,改进的算法就是从root开始递归检查每个子树的高度,如果子树是平衡的,那么就返回子树的高度,否则返回-1:递归结束,树是不平衡的。
int checkHeight(const TreeNode* root){
if( root == nullptr){
return 0;
}
// check the left subtree is balanced or not.
int leftHeight = checkHeight(root->leftChild);
if( leftHeight == -1 ){
return -1;
} // check the right subtree is balanced or not.
int rightHeight = checkHeight(root->rightChild);
if( rightHeight == -1){
return -1;
} // check the current tree is balanced or not.
int diff = leftHeight - rightHeight;
if( abs(diff) > 1){
return -1;
}
else{
// return the tree height.
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(const TreeNode* root){
return ( checkHeight(root) == -1 )? false:true;
}
由于每个node只会访问一次,因此算法时间复杂度为O(n)。但是需要额外的O(logn)的空间。
最新文章
- fir.im Log Guru 正式开源,快速找到 iOS 应用无法安装的原因
- maven 项目出现 java.lang.ClassNotFoundException
- 给深度学习入门者的Python快速教程 - 基础篇
- 【linux】学习1
- Yii源码阅读笔记(二十七)
- Machine Learning – 第2周(Linear Regression with Multiple Variables、Octave/Matlab Tutorial)
- 第一部分 CLR基础:第1章 CLR的执行模型
- ccnu-线段树联系-单点更新2-B
- php随机验证码
- [改善Java代码]三元操作符的类型务必一致
- zabbix之2安装编译/基本功能实现
- ZOJ 3594 年份水题 【注意:没有0年】
- 如何在asp.net页面使用css和js
- 1.2低级线程处理API
- java.util.Map
- 如何通过 Terminal 设置截图存储的位置
- AI1.1-人工智能史
- C#遍历可变化的集合
- block本质探寻四之copy
- 凡事不求甚解,遇事必定抓瞎——PHP开发Apache服务器配置备忘录