今天面试一个实习生,就想既然是未出校园,那就出一个比较基础的题吧,没想到答的并不如人意,对于树的操作完全不熟悉,因此此题算是未作答。原来我想看一下他分析问题的思路,优化代码的能力。接下来会把最近半年我出的面试题整理出来,以来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)的空间。
分享到:
相关推荐
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各...
C++信号放大器 (1) 运用二叉树的定义将左孩子、右孩子、结点值、权值即与父结点的衰减量、以及...结点信息的输入也比较麻烦,很浪费时间,还有就是输出结果时最好将二叉树的具体结构一同输出便于检查,并且形象直观。
书中使用的软件工程原则和概念以及UML图便于增强学生的理解。 ◆ 详细介绍了数据抽象,强调规范和实现之间的区别 ◆ 广泛介绍了各种面向对象的编程技术 ◆ 重点是核心的数据结构,而不是非必要的C++语言语法 ◆ ...
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
如果希望实现这些算法中的任何一个,就会发现,将书中的伪代码翻译成读者熟悉的某种程序设计语言,是一件相当直接的事。伪代码被设计成能够清晰简明地描述每一个算法。因此,我们不考虑出错处理和其他需要对读者所用...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
(2)从文件A读入30个无序整数,建立一个递增的单链表A并输出,从文件B读入30个无序整数,建立一个递增的单链表B并输出,在A中求递增的并集。 (3)从文件读入30个学生成绩(0-100之间),建立一个双向循环链表并...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
如果希望实现这些算法中的任何一个,就会发现,将书中的伪代码翻译成读者熟悉的某种程序设计语言,是一件相当直接的事。伪代码被设计成能够清晰简明地描述每一个算法。因此,我们不考虑出错处理和其他需要对读者所用...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*, char*const的区别 36 7. C中可变参数函数实现 38 8. C程序内存中组成部分 41 9. C编程拾粹 42 10. C语言中实现数组的动态...
算法描述:在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除...
• 数组(静态数组、动态数组)、线性表、链表(单向链表、双向链表、循环链表)、队列、栈、树(二叉树、查找树、平衡树、线索树、线索树、堆)、图等的定义、存储和操作 • Hash(存储地址计算,冲突处理) ...
C/C++实现冒泡排序算法 ................................................................................................................. 29 5. C++中指针和引用的区别 ......................................