目录
- 前言
- 题目
- 1.求高度和深度的区别
- 节点的高度
- 节点的深度
- 2. 本题思路分析:
- 3. 算法实现
- 4. pop函数的算法复杂度
- 5. 算法坑点
前言
在本科毕设结束后,我开始刷卡哥的“代码随想录”,每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接
题目
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
1.求高度和深度的区别
节点的高度
求节点的高度指的是该节点到叶子节点的最长简单路径的节点数,
求节点的高度,递归方法时记得使用后序遍历
但是求根节点的高度就是求二叉树的最大深度
节点的深度
求节点的深度指的是根节点到该节点的最长简单路径的节点数
求节点的深度,递归方法时记得使用前序遍历
2. 本题思路分析:
- 使用后续遍历,因为求的是节点的高度,求出节点的左右孩子的高度,进行比较,如果差值大于1则代表不是平衡二叉树,向父节点返回-1,告知父节点此树不为平衡二叉树;
- 否则返回当前节点的高度,当前节点的高度是,左右子树的最大值+1就是当前节点的高度。
3. 算法实现
- 代码:
//递归法(后序遍历)因为是求高度,所以是后序遍历
//求高度,所以使用后序遍历
public boolean isBalanced(TreeNode root) {return getHeightOfTree(root) == -1 ? false :true;
}
//递归三部曲
//1.确定返回值和参数 返回值是深度 参数是以当前节点 如果是平衡二叉树则返回树的高度,否则返回-1
//2.确定返回条件
//3.确定单层递归逻辑
public int getHeightOfTree(TreeNode root){if(root == null){return 0;}int leftHeight = getHeightOfTree(root.left);if(leftHeight == -1){//左子树不为平衡二叉树return -1;}int rightHeight = getHeightOfTree(root.right);if(rightHeight == -1){//右子树不为平衡二叉树return -1;}if(Math.abs(leftHeight - rightHeight) <= 1){//该节点为根节点的树不为平衡二叉树return 1 + Math.max(leftHeight , rightHeight); }else{return -1;}}
4. pop函数的算法复杂度
n为总结点数
时间复杂度:O(log n × log n)
空间复杂度:O(log n)
5. 算法坑点
暂无