推荐
完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版
题目描述
题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int left = getDepth(root.left);
if (left == -1)
return -1;
int right = getDepth(root.right);
if (right == -1)
return -1;
if (Math.abs(left - right) > 1)
{
return -1;
} else {
return Math.max(left, right) + 1;
}
}
}
思路: 递归 + 剪枝
递归检查子树是否是平衡二叉树
一旦发现某个子树不是平衡二叉树,则不用再继续检查下去了。
实现:
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int left = getDepth(root.left);
if (left == -1)
return -1;
int right = getDepth(root.right);
if (right == -1)
return -1;
if (Math.abs(left - right) > 1)
{
return -1;
} else {
return Math.max(left, right) + 1;
}
}
}
看完之后,如果还有什么不懂的,可以在评论区留言,会及时回答更新。
这里是猿兄,为你分享程序员的世界。
非常感谢各位大佬们能看到这里,如果觉得文章还不错的话, 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用!!!
注: 如果猿兄这篇博客有任何错误和建议,欢迎大家留言,不胜感激!