LeetCode - Balanced Binary Tree
Problem description
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 left and right subtrees of every node differ in height by no more than 1.
Example 1:
1
2
3
4
5
6
7
8
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
1
2
3
4
5
6
7
8
9
10
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
Analysis
The main idea is to check if the height of two subtrees differ by more than 1.
An important point is that you should only compare height of two subtree but not all the depth. (balanced tree and complete tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean balanced = true;
public boolean isBalanced(TreeNode root) {
if (root == null){
return true;
}
dfs(root, 0);
return balanced;
}
int dfs(TreeNode node, int depth){
if (node == null){
return depth;
}
int left = dfs(node.left, depth+1);
int right = dfs(node.right, depth + 1);
if (Math.abs(left-right) >= 2){
balanced = false;
}
return Math.max(left, right);
}
}
What to improve
- be careful about the definition of different types of tree.