题目#110.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树[3,9,20,null,null,15,7]
返回true 。
示例 2:
给定二叉树[1,2,2,3,3,null,null,4,4]
返回false 。
分析
平衡二叉树需要左右子树高度差不超过1，所以我们需要一个计算二叉树高度的方法，然后再计算高度的同时递归判断左右子树高度，如果相差超过1，则不是平衡二叉树。
代码
import kotlin.math.*
private var flag = true
fun isBalanced(root: TreeNode?): Boolean {
high(root)
return flag
}
private fun high(root: TreeNode?): Int {
if (root == null) return 0
val left = high(root.left)
val right = high(root.right)
if (abs(left - right) > 1) flag = false
return 1 + max(left, right)
}
代码分析
在求二叉树高度的递归中，将左右子树的高度做差，如果不满足，则flag设为false，但是这么做其实是有一定问题的，因为flag可能早早的就已经是false了，就是说已经很早就能判定这个二叉树并不是平衡二叉树了，但是程序依然还在计算子树的高度，这样让时间复杂度大大提高了，我们需要适当的剪枝。
优化
fun isBalanced(root: TreeNode?): Boolean {
high(root)
return flag
}
private fun high(root: TreeNode?): Int {
if (root == null || !flag) return 0
val left = high(root.left)
val right = high(root.right)
if (abs(left - right) > 1) flag = false
return 1 + max(left, right)
}
优化后的代码分析
- 使用
if (root == null || !flag) return 0代替if (root == null) return 0，从而让程序能在已经判断不是平衡二叉树的时候早早的退出循环，进而提高效率。
