110 Balanced Binary Tree

110. Balanced Binary Tree

1. Question

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.

2. Implementation

(1) DFS
1
class Solution {
2
public boolean isBalanced(TreeNode root) {
3
if (root == null) {
4
return true;
5
}
6
7
return dfs(root) != -1;
8
}
9
10
public int dfs(TreeNode node) {
11
if (node == null) {
12
return 0;
13
}
14
15
int leftHeight = dfs(node.left);
16
int rightHeight = dfs(node.right);
17
18
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
19
return -1;
20
}
21
return Math.max(leftHeight, rightHeight) + 1;
22
}
23
}
Copied!

3. Time & Space Complexity

DFS: 时间复杂度: O(n), 空间复杂度: O(h)