1382. Balance a Binary Search Tree

题目信息

题号:

1382

难度:

Medium

主题:

二叉搜索树、中序遍历、平衡构造

原题:

LeetCode 1382

重点:

返回包含相同节点值的一棵平衡二叉搜索树;每个节点左右子树高度差不超过一,答案不唯一

题目重述

给定一棵二叉搜索树 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]
解释:无需改变结构。