题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
所谓平衡二叉树就对某个结点来讲，其左子树的深度与右子树深度的绝对值不超过1。由于需要对每个节点进行判断，所以可以采用递归的思路进行解决。具体思路是：先求出根节点的左右子树的深度，并对两者进行判断，如果没有满足左右子树的深度的绝对值不超过1的条件，那么就不是平衡二叉树。下一步，自然就是分别对根节点的左右子树进行递归判断了，这样一直到叶子结点。整棵二叉树的所有节点都判断完毕，所以这个问题就解决了。下面是这种思路的实现代码（已被牛客AC）：
package com.rhwayfun.offer;
public class IsBiTreeBalanced {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) return true;
int leftLen = TreeDepth(root.left);
int rightLen = TreeDepth(root.right);
int lenDif = leftLen - rightLen;
if(lenDif < -1 || lenDif > 1) return false;
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int TreeDepth(TreeNode root) {
if(root == null) return 0;
int leftLen = TreeDepth(root.left);
int rightLen = TreeDepth(root.right);
return leftLen > rightLen ? leftLen + 1 : rightLen + 1;
}
public static void main(String[] args) {
}
}
AI 代码解读
