LeetCode110-平衡二叉树

LeetCode110-平衡二叉树

递归实现(O(n))

递归判断左右两颗子树的高度,如果高度差超过1,就不是平衡二叉树,并且只要左右两边有一个不是,整棵树就都不是平衡二叉树,如果不加leftHeight == -1 || rightHeight == -1这两个,就会把所有的都子树的子树的子树…都判断一遍,浪费性能,也可以递归isBalanced()方法,传进去左右子树的结点进行判断,这样反而让时间复杂度变成O(n^2)了,二叉树的递归其实是把每个结点都走一遍,所以O(n),两层递归就是O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}

public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}

双递归实现(O(n^2))

1
2
3
4
5
6
7
8
9
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right)) <= 1;
}

private int height(TreeNode root) {
if (root == null) return 0;
return Math.max(height(root.left), height(root.right)) + 1;
}