1382. Balance a Binary Search Tree¶
题目信息¶
- 题号:
1382
- 难度:
Medium
- 主题:
二叉搜索树、中序遍历、平衡构造
- 原题:
- 重点:
返回包含相同节点值的一棵平衡二叉搜索树;每个节点左右子树高度差不超过一,答案不唯一
题目重述¶
给定一棵二叉搜索树 root,其中节点值互不相同。请重新组织这些值,构造一棵高度平衡的二叉搜索树。
新树必须包含原树全部节点值且不多不少,并继续满足搜索树性质。任意合法平衡结构均可返回。
树中节点数在 [1,10^4],节点值位于 [1,10^5]。
自建示例¶
右斜链可以重组为平衡结构:
输入:root = [1,null,2,null,3,null,4]
输出:[2,1,3,null,null,null,4]
解释:新树中序序列仍为 1、2、3、4,且各节点左右子树高度差不超过一。
单节点树已经平衡:
输入:root = [7]
输出:[7]
解释:无需改变结构。