我在一本书中看到了这个问题(破解编码面试)。建议代码为:
public boolean isBalanced(Node root) {
if(root == null)
return true;
int leftHeight = getHeight(root.left);
System.out.println("left height: " + leftHeight);
int rightHeight = getHeight(root.right);
System.out.println("right height: " + rightHeight);
int diff = Math.abs(leftHeight - rightHeight);
// check if difference in height is more than 1
if (diff > 1)
return false;
// check if left and right subtrees are balanced
else
return isBalanced(root.left) && isBalanced(root.right);
我不明白的是为什么我们需要returnisbalanced(root.left)和&isbalanced(root.right)。仅仅检查高度就足够了吗?如果高度大于1,返回false,否则返回true?
1条答案
按热度按时间cl25kdpy1#
不,仅检查高度是不够的,如果高度大于1,则返回false,否则返回true。简单地检查根的高度会导致如下误报: