0%

将二叉搜索树变平衡


题目描述

给你一棵二叉搜索树,请你返回一棵平衡后的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 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] 也是一个可行的构造方案。

提示:

  1. 树节点的数目在 1 到 10^4 之间。
  2. 树节点的值互不相同,且在 1 到 10^5 之间。

题解

「平衡」要求它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1,这很容易让我们产生这样的想法——左右子树的大小越「平均」,这棵树会不会越平衡?于是一种贪心策略就形成了:我们可以通过中序遍历将原来的二叉搜索树转化为一个有序序列,然后对这个有序序列递归建树,对于区间 [L, R]:

  • mid = (L + R) / 2,即中心位置做为当前节点的值。
  • 如果 L ≤ mid − 1,那么递归地将区间 [L, mid − 1] 作为当前节点的左子树。
  • 如果 mid + 1 ≤ R,那么递归地将区间 [mid + 1, R] 作为当前节点的右子树。

经过证明此方法是可行的,关于证明方式在此不做赘述,想要了解的同学可以参考下面官方的题解。

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
List<Integer> treeValList = new ArrayList<>();

public TreeNode balanceBST(TreeNode root) {
dfsGetTreeValList(root);
return buildBalanceBST(0, treeValList.size() - 1);
}

private TreeNode buildBalanceBST(int left, int right) {
int mid = right - ((right - left) >> 1);
TreeNode node = new TreeNode(treeValList.get(mid));
node.left = left < mid ? buildBalanceBST(left, mid - 1) : null;
node.right = mid < right ? buildBalanceBST(mid + 1, right) : null;
return node;
}

private void dfsGetTreeValList(TreeNode node) {
if (node == null) {
return;
}
dfsGetTreeValList(node.left);
treeValList.add(node.val);
dfsGetTreeValList(node.right);
}

public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

复杂度分析

  • 时间复杂度:O(n),获得中序遍历的时间代价是 O(n);建立平衡二叉树的时建立每个点的时间代价为 O(1),总时间也是 O(n)。故渐进时间复杂度为 O(n)。
  • 空间复杂度:O(n),这里使用了一个数组作为辅助空间,存放中序遍历后的有序序列,故渐进空间复杂度为 O(n)。

来源

将二叉搜索树变平衡 | 力扣(LeetCode)
将二叉搜索树变平衡 | 题解(LeetCode)


文章标题:将二叉搜索树变平衡
文章作者:cylong
文章链接:http://www.cylong.com/blog/2020/08/20/balance-a-binary-search-tree/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)

欢迎关注我的其它发布渠道