一、题目
1、算法题目
“给定一个二叉树，判断它是否是平衡二叉树。”
题目链接：
来源：力扣（LeetCode）
链接： 110. 平衡二叉树
2、题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
网络异常，图片无法展示
|
示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： true 复制代码
示例 2： 输入： root = [1,2,2,3,3,null,null,4,4] 输出： false 复制代码
二、解题
1、思路分析
这出题的顺序就不能由易到难吗，前面几道题这么难，这道题这么简单。
这道题是判断给定的二叉树是不是平衡二叉树，如果一棵二叉树是平衡二叉树，那么其所有子树也是平衡二叉树。
那么就可以递归地判断二叉树是不是平衡二叉树。
2、代码实现
代码参考：
class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; } else { return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } } public int height(TreeNode root) { if (root == null) { return 0; } else { return Math.max(height(root.left), height(root.right)) + 1; } } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n2)
其中n是二叉树中的节点个数。二叉树是满二叉树，需要遍历二叉树中所有节点，时间复杂度为O(n)，对于最坏的情况，二叉树形成链式结构，高度为O(n)，因此总时间复杂度为O(n2)。
空间复杂度： O(n)
其中n是二叉树的节点个数，空间发咋读取决于递归调用的层数，递归调用的层数不会超过n。
三、总结
计算节点高度，就可以判断二叉树是否平衡。
比如遍历到当前节点，计算左右子树的高度，如果左右子树的高度差不超过1，说明这个是根节点。
然后再分别遍历左右子树，判断左右子树是否平衡。
