-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathisBalancedTree.java
More file actions
49 lines (40 loc) · 1.2 KB
/
isBalancedTree.java
File metadata and controls
49 lines (40 loc) · 1.2 KB
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
43
44
45
46
47
48
49
/**
* 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 * of every node never differ by more than 1.
*/
// Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
//This solution only care for height of the tree, not care how many node in each tree
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) { //empty tree
return true;
}
if (getHeight(root) == -1) {
return false;
}
return true;
}
//Get height of given tree
public int getHeight(TreeNode root) {
if (root == null)
return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
if (left == -1 || right == -1) {
return -1;
}
if (Math.abs(left - right) > 1) { //inbalanced tree, height between left and right node is not equal
return -1;
}
//return height of the tree
return Math.max(left, right) + 1;
}
}