题目描述(简单难度)
判断一棵树是否是平衡二叉树,平衡二叉树定义如下:
解法一
直接按照定义来吧,并且多定义一个求高度的函数,之前在 104 题 做过。
解法二
大家觉不觉得解法一怪怪的,有一种少了些什么的感觉,自己写之前就有这种感觉,写完以后仔细分析了一下。
当我们求左子树的高度时,同样是利用了递归去求它的左子树的高度和右子树的高度。
当代码执行到
第二个不好的地方在于, getTreeDepth
递归的求高度的时候,也是求了左子树的高度,右子树的高度,此时完全可以判断当前树是否是平衡二叉树了,而不是再继续求高度。
综上,我们其实只需要求一次高度,并且在求左子树和右子树的高度的同时,判断一下当前是否是平衡二叉树。
考虑到 getTreeDepth
函数返回的是int
值,同时高度不可能为负数,那么如果求高度过程中我们发现了当前不是平衡二叉树,就返回-1
。
上边的代码还是有问题的,
int leftDepth = getTreeDepth(root.left);
int rightDepth = getTreeDepth(root.right);
如果左右子树都不是平衡二叉树,此时都返回了-1
,那么再执行下边的代码。
它们的差会是 0,不会进入if
中,但是本来应该进入 if
返回 -1
的。
private int getTreeDepth(TreeNode root) {
return 0;
}
int leftDepth = getTreeDepth(root.left);
if (leftDepth == -1) {
return -1;
int rightDepth = getTreeDepth(root.right);
return -1;
}
if (Math.abs(leftDepth - rightDepth) > 1) {
return -1;
}
return Math.max(leftDepth, rightDepth) + 1;
}
对于我们要写的 isBalanced
函数,修改的话就简单了,只需要调用一次 getTreeDepth
函数,然后判断返回值是不是就可以了。
总
还是比较简单的,有时候可能一下子想不到最优的思路,所以可以先把常规的想法先写出来以便理清思路,然后尝试着去优化。
添加好友一起进步~
如果觉得有帮助的话,可以点击 给一个 star 哦 ^^
如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情