【Leetcode】【Easy】Balanced Binary Tree
2024-10-19 01:02:49
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
错误的思路(o(N2)时间复杂度):
写一个函数a,用递归遍历的方法,用于计算当前结点的高。
主函数从根节点开始,调用a计算其左子结点和右子结点高差值(×N),如果大于1则返回false,如果小于等于1则继续以左子结点和右子节点分别为根(×N),测试其平衡性;
正确的思路(o(N)时间复杂度):
错误的思路没有正确理解递归。判断平衡二叉树的条件是:①左子树是平衡的;②右子树是平衡的;③左子树和右子树的深度相差不超过1;
因此每一层递归只需要做两件事,判断左右子树是否平衡,判断左右子树深度差。
这样一来,遍历一遍即可获得判定结果。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode *root) {
int dep = ;
return checkBalance(root, &dep);
} bool checkBalance(TreeNode *node, int *dep) {
if (node == NULL)
return true; int leftDep = ;
int rightDep = ;
if (checkBalance(node->left, &leftDep) &&
checkBalance(node->right, &rightDep) &&
(abs(rightDep - leftDep) <= )) {
*dep = max(leftDep, rightDep) + ;
return true;
} else {
return false;
}
}
};
最新文章
- variadic function 的使用
- nlp
- [转]在ASP.NET开发中容易忽略的2个小问题 Cookie乱码存取异常 和 iframe弹框的login跳转
- cantor三分集
- mysql存储过程性能监控和分析
- 汉诺塔问题II(模拟)
- rman的conver方法拷贝ASM文件
- Android Studio学习随笔-基本事件(点击)
- 2015 11 26 java 配置环境变量
- Serializable 作用
- MySQL字符串相关函数学习二
- Swift基础之显示波纹样式
- BEX5下实现鼠标滚动滚动条
- py库: pyautogui (自动测试模块,模拟鼠标、键盘动作)
- [android] 新闻客户端主界面部分
- reboot 后 Docker服务及容器自动启动设置
- 【数组】Set Matrix Zeroes
- tomcat配置管理员帐号密码
- bzoj 3195 奇怪的道路
- ffmpeg截取一段视频中一段视频