算法热题：II. 平衡二叉树
题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4]
返回 false 。
今天的这个题目其实可以和联动起来。判断一颗二叉树是否平衡，其实只要递归计算出两个子树的最大深度，如果发现超过 1 的就直接返回 false 即可。
所以结合昨天的代码，很容易写出以下的答案：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
时间复杂度：O(n^2)，空间复杂度：O(n)
但是可以看出，这个答案有好多重复计算，从根节点开始计算，没问题在从左右子树开始，等于叶子节点会被遍历多很多次，这属于从顶到底的遍历。
那么我们可以优化一下，从底部开始往顶遍历，一遇到不平衡就直接返回，这样就省去的那些重复计算。
代码很清晰，还是递归，只是先计算底部左右子树的深度进行比较。
class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth(root) >= 0;
}
private int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
if (leftDepth == -1) { //说明左子树已经不符合规则
return -1;
}
int rightDepth = maxDepth(root.right);
if (rightDepth == -1) { //说明右子树已经不符合规则
return -1;
}
if (Math.abs(leftDepth - rightDepth) > 1) {
return -1;
}
return 1 + Math.max(leftDepth, rightDepth);
}
}
时间复杂度：O(n)，空间复杂度：O(n)
一道简单题。
点击阅读原文即可练习。