[剑指Offer]判断一棵树为平衡二叉树（递归）
2024-10-19 08:59:35
题目链接
题意
判断一棵树是否为平衡二叉树
思路
法一，定义版：按定义，自上而下遍历树，会有重复计算。
法二，优化版：自下而上遍历树，若不平衡则返回-1，至多遍历树一遍。
相关知识
平衡二叉树：或空树，或根结点左右子树高度差<=1,且左右子树也为平衡二叉树。
代码
定义版
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL){return true;}
else if(abs(getDepth(pRoot->left)-getDepth(pRoot->right))<=1){
return true;
}
return false;
}
private:
int getDepth(TreeNode* pRoot){
if(pRoot==NULL){return true;}
else return max(getDepth(pRoot->left),getDepth(pRoot->right))+1;
}
};
优化版
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
return getDepth(pRoot)!=-1;
}
private:
int getDepth(TreeNode* pRoot){
if(pRoot==NULL){return 0;}
else{
int left=getDepth(pRoot->left);
if(left==-1){return -1;}
int right=getDepth(pRoot->right);
if(right==-1){return -1;}
if(abs(right-left)>1){return -1;}
else{return max(left,right)+1;}
}
}
};
最新文章
- spring 定时任务配置
- 【大数据技巧】日均2TB日志数据在线快速处理之法
- ajax 参数有中文
- 重拾java系列一java基础（1）
- Java文件读写
- 深入分析Java的序列化与反序列化
- SharePoint 2010 升级到2013时间 为了确保用户可以连接，但无法改变升级数据
- DOS批处理的字符串功能
- 手机自动化测试：appium源码分析之bootstrap十二
- MySQL监听数据库存储过程出现异常
- 理解Python中的yield
- 简易promise的实现（二）
- 隔离 docker 容器中的用户
- pycharm的快捷键
- insmod 签名问题
- free(): invalid next size (fast): 0x000000xxx
- nasm学习资料
- gdb调试多进程多线程程序
- db2 backup export
- Centos7下python3安装pip-9.0.1