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