Given the root of a binary search tree, return a balanced binary search tree that contains the same node values. If there is more than one valid answer, return any of them.
A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.
Example:
Input: root = [1, null, 2, null, 3, null, 4, null, null]
Output: [2, 1, 3, null, null, null, 4]
(Other balanced shapes with the same values are also acceptable.)
先中序遍历得到 递增数组 ，再用“ 有序数组构建平衡 BST”的方法递归选取中点为根构建整棵树。时间 O(n)，额外空间 O(n)。
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 OpenAI、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
正文完
