友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
解题分析
-
对二叉树做深度优先遍历DFS，递归过程中：
-
终止条件：当DFS越过叶子节点时，返回高度0；
-
返回值：
-
从底至顶，返回以每个节点
root为根节点的子树最大高度(左右子树中最大的高度值加1max(left,right) + 1)； -
当我们发现有一例
左/右子树高度差 ＞ 1的情况时，代表此树不是平衡树，返回-1；
-
-
当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回-1，避免后续多余计算。
-
-
最差情况是对树做一遍完整DFS，时间复杂度为 O(N)。
这里有个思维误区：并不是最顶层的左右树相差不超过 1 就是平衡树；而是递归定义的，是每棵树的左右子树的高度差都不能超过 1 才可以。
-
一刷
-
二刷（树形DP）
-
二刷（优化剪枝）
-
三刷
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
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Balanced Binary Tree.
* Memory Usage: 41.4 MB, less than 11.11% of Java online submissions for Balanced Binary Tree.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-02-06 23:10
*/
public boolean isBalanced(TreeNode root) {
return depth(root) != -1;
}
private int depth(TreeNode root) {
if (Objects.isNull(root)) {
return 0;
}
int left = depth(root.left);
if (left == -1) {
return -1;
}
int right = depth(root.right);
if (right == -1) {
return -1;
}
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
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
/**
* 使用“树形 DP 套路”
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-21 23:25
*/
public boolean isBalanced(TreeNode root) {
return dfs(root).balance;
}
public Record dfs(TreeNode root) {
if (root == null) {
return new Record(true, 0);
}
Record left = dfs(root.left);
Record right = dfs(root.right);
boolean balance = left.balance && right.balance && Math.abs(left.height - right.height) <= 1;
return new Record(balance, Math.max(left.height, right.height) + 1);
}
public static class Record {
public boolean balance;
public int height;
public Record(boolean balance, int height) {
this.balance = balance;
this.height = height;
}
}
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
/**
* 看了论坛中大家的讨论，做了提前结束递归的优化。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-23 00:28
*/
public boolean isBalanced(TreeNode root) {
return dfs(root) >= 0;
}
public int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
// 发现不平衡即提前结束递归
if (left < 0) {
return -1;
}
int right = dfs(root.right);
// 发现不平衡即提前结束递归
if (right < 0) {
return -1;
}
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-18 22:28:21
*/
public boolean isBalanced(TreeNode root) {
return dfs(root) >= 0;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
if (left < 0) {
return left;
}
int right = dfs(root.right);
if (right < 0) {
return right;
}
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}
树形 DP 解法参考了：Dynamic Programming 动态规划 中介绍的 “树形 DP 套路” 解法。
参考论坛中大家的讨论，可以在发现不平衡时，就及时返回，停止执行其他相关递归调用，起到“剪枝”的作用。同时，时间复杂度也可以做到最好。