代码随想录-51-110.平衡二叉树

前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

1.求高度和深度的区别

节点的高度

求节点的高度指的是该节点到叶子节点的最长简单路径的节点数，
求节点的高度，递归方法时记得使用后序遍历
但是求根节点的高度就是求二叉树的最大深度

节点的深度

求节点的深度指的是根节点到该节点的最长简单路径的节点数
求节点的深度，递归方法时记得使用前序遍历

2. 本题思路分析：

1. 使用后续遍历，因为求的是节点的高度，求出节点的左右孩子的高度，进行比较，如果差值大于1则代表不是平衡二叉树，向父节点返回-1，告知父节点此树不为平衡二叉树；
2. 否则返回当前节点的高度，当前节点的高度是，左右子树的最大值+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. 算法坑点

暂无