友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1382. 将二叉搜索树变平衡
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1，我们就称这棵二叉搜索树是 平衡的 。
示例 1：
输入：root = [1,null,2,null,3,null,4,null,null] 输出：[2,1,3,null,null,null,4] 解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
示例 2：
输入: root = [2,1,3] 输出: [2,1,3]
提示：
-
树节点的数目在
[1, 104]范围内。 -
1 <= Node.val <= 105
思路分析
二叉搜索树，先中序遍历拿到所有节点，然后递归构造平衡二叉搜索树。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-31 22:12:20
*/
public TreeNode balanceBST(TreeNode root) {
List<TreeNode> data = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
TreeNode mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
}
data.add(cur);
cur = cur.right;
}
TreeNode result = dfs(data, 0, data.size() - 1);
return result;
}
private TreeNode dfs(List<TreeNode> data, int start, int end) {
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;
TreeNode node = data.get(mid);
node.left = dfs(data, start, mid - 1);
node.right = dfs(data, mid + 1, end);
return node;
}