110. Balanced Binary Tree#
Brute-force#
1class Solution {
2
3 public boolean isBalanced(TreeNode root) {
4 return dfsHeight(root) != -1;
5 }
6
7 private int dfsHeight(TreeNode node) {
8 if (node == null) {
9 return 0;
10 }
11
12 int leftHeight = dfsHeight(node.left);
13 if (leftHeight == -1) {
14 return -1;
15 }
16
17 int rightHeight = dfsHeight(node.right);
18 if (rightHeight == -1) {
19 return -1;
20 }
21
22 if (Math.abs(leftHeight - rightHeight) > 1) {
23 return -1;
24 }
25
26 return Math.max(leftHeight, rightHeight) + 1;
27 }
28}
Time Complexity |
Space Complexity |
|---|---|
\(\mathcal{O}(n^2)\) |
\(\mathcal{O}(1)\) |
Optimized DFS#
1class Solution {
2
3 public boolean isBalanced(TreeNode root) {
4 return dfsHeight(root) != -1;
5 }
6
7 private int dfsHeight(TreeNode node) {
8 if (node == null) {
9 return 0;
10 }
11
12 int leftHeight = dfsHeight(node.left);
13 if (leftHeight == -1) {
14 return -1;
15 }
16
17 int rightHeight = dfsHeight(node.right);
18 if (rightHeight == -1) {
19 return -1;
20 }
21
22 if (Math.abs(leftHeight - rightHeight) > 1) {
23 return -1;
24 }
25
26 return Math.max(leftHeight, rightHeight) + 1;
27 }
28}
Time Complexity |
Space Complexity |
|---|---|
\(\mathcal{O}(n)\) |
\(\mathcal{O}(1)\) |