forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
balancedBinaryTree.java
57 lines (51 loc) · 1.84 KB
/
balancedBinaryTree.java
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
50
51
52
53
54
55
56
57
// Source : https://oj.leetcode.com/problems/balanced-binary-tree/
// Inspired by : https://www.jiuzhang.com/solutions/balanced-binary-tree/
// Author : Lei Cao
// Date : 2015-10-07
/**********************************************************************************
*
* 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.
* Example
* Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
* The binary tree A is a height-balanced binary tree, but B is not.
**********************************************************************************/
package balancedBinaryTree;
/**
* Created by leicao on 7/10/15.
*/
public class balancedBinaryTree {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
// write your code here
return helper(root, 0).isBalanced;
}
// This is not needed. Can just check the depth
private class Result {
boolean isBalanced;
int height;
Result(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
private Result helper(TreeNode root, int depth) {
if (root == null) {
return new Result(true, depth);
}
Result left = helper(root.left, depth + 1);
Result right = helper(root.right, depth + 1);
if (!left.isBalanced || !right.isBalanced) {
return new Result(false, 0);
}
if (Math.abs(left.height - right.height) > 1) {
return new Result(false, 0);
}
return new Result(true, Math.max(left.height, right.height));
}
}