当前位置 博文首页 > 数据结构和算法：剑指 Offer-平衡二叉树
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
//计算树中节点的高度
public int depth(TreeNode root) {
if (root == null)
return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
所以这题的代码我们也很容易写出来
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
//分别计算左子树和右子树的高度
int left = depth(root.left);
int right = depth(root.right);
//这两个子树的高度不能超过1
return Math.abs(left - right) <= 1;
}
//计算树中节点的高度
public int depth(TreeNode root) {
if (root == null)
return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
视频链接
再来看下代码
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
//分别计算左子树和右子树的高度
int left = depth(root.left);
int right = depth(root.right);
//这两个子树的高度不能超过1，并且他的两个子树也必须是平衡二叉树
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
//计算树中节点的高度
public int depth(TreeNode root) {
if (root == null)
return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
视频链接
先判断两个子树是否是平衡的，然后再判断以当前节点为根节点的子树是否是平衡的……。来看下代码
//如果等于-1就表示不是平衡的
private static final int UNBALANCED = -1;
public boolean isBalanced(TreeNode root) {
return helper(root) != UNBALANCED;
}
public int helper(TreeNode root) {
if (root == null)
return 0;
//如果左子节点不是平衡二叉树，直接返回UNBALANCED
int left = helper(root.left);
if (left == UNBALANCED)
return UNBALANCED;
//如果右子节点不是平衡二叉树，直接返回UNBALANCED
int right = helper(root.right);
if (right == UNBALANCED)
return UNBALANCED;
//如果左右子节点都是平衡二叉树，但他们的高度相差大于1，
//直接返回UNBALANCED
if (Math.abs(left - right) > 1)
return UNBALANCED;
//否则就返回二叉树中节点的最大高度
return Math.max(left, right) + 1;
}
