leetcode-java/src/BalancedBinaryTree110.java at master · fluency03/leetcode-java · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * 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 a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */


publicclassBalancedBinaryTree110 {

publicbooleanisBalanced(TreeNoderoot) {
if (root == null) {
returntrue;
 }

intdepthL = depth(root.left);
intdepthR = depth(root.right);

returnMath.abs(depthL - depthR) <= 1 && isBalanced(root.left) && isBalanced(root.right);

 }

privateintdepth(TreeNodenode) {
if (node == null) {
return0;
 }

intdepthL = depth(node.left);
intdepthR = depth(node.right);

returnMath.max(depthL, depthR) + 1;
 }


/**
 * https://discuss.leetcode.com/topic/11007/java-solution-based-on-height-check-left-and-right-node-in-every-recursion-to-avoid-further-useless-search
 */
publicbooleanisBalanced2(TreeNoderoot) {
if (root == null) {
returntrue;
 }
returnheight(root) != -1;

 }

publicintheight(TreeNodenode){
if (node == null) {
return0;
 }

intlH = height(node.left);
if (lH == -1) {
return -1;
 }

intrH = height(node.right);
if (rH == -1) {
return -1;
 }

if (lH-rH < -1 || lH-rH > 1) {
return -1;
 }

returnMath.max(lH,rH) + 1;
 }


publicstaticvoidmain(String[] args) {
BalancedBinaryTree110bbt = newBalancedBinaryTree110();

TreeNoderoot1 = newTreeNode(2);
root1.left = newTreeNode(1);
root1.right = newTreeNode(3);

TreeNoderoot3 = newTreeNode(2);
root3.left = newTreeNode(1);

TreeNoderoot2 = newTreeNode(2);
root2.left = root3;


TreeNoden1 = newTreeNode(1);
TreeNoden2 = newTreeNode(2);
TreeNoden3 = newTreeNode(3);
TreeNoden4 = newTreeNode(4);
TreeNoden5 = newTreeNode(5);
TreeNoden6 = newTreeNode(6);
TreeNoden7 = newTreeNode(7);
TreeNoden8 = newTreeNode(8);

n4.left = n7;
n2.left = n4;
n2.right = n5;
n1.left = n2;

n6.right = n8;
n3.right = n6;
n1.right = n3;


System.out.println("-------- 1");
System.out.println(bbt.isBalanced(root1));
System.out.println("-------- 2");
System.out.println(bbt.isBalanced(root2));
System.out.println("-------- 3");
System.out.println(bbt.isBalanced(root3));
System.out.println("-------- 4");
System.out.println(bbt.isBalanced(n1));
 }
}