※ 引述 《sustainer123 (caster)》 之铭言：
:
: https://leetcode.com/problems/balance-a-binary-search-tree
:
: 给定一二元搜寻树 请回传有相同节点值的平衡二元搜寻树
:
: 如果有多个 请回传任一个即可
:
: 假如左右子树深度相差不超过1 此即为平衡二元搜寻树
:
: Example 1:
:
:
: Input: root = [1,null,2,null,3,null,4,null,null]
: Output: [2,1,3,null,null,null,4]
: Explanation: This is not the only correct answer, [3,1,4,null,2] is also
: correct.
: Example 2:
思路:
一样
我好恨树
每次都卡一堆小鸡巴细节
好烦
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), ri
ght(right) {}
* };
*/
class Solution {
public:
vector<int> paper;
void go(TreeNode* root)
{
if(root==NULL)return;
go(root->left);
paper.push_back(root->val);
go(root->right);
return;
}
void build(TreeNode* p,int l , int r)
{
p->val = paper[(l+r)/2];
if(l>r)return ;
if(l <= (l+r)/2-1)
{
TreeNode* pl = new TreeNode();
p->left = pl;
build(pl,l,(l+r)/2-1);
}
if((l+r)/2+1 <= r)
{
TreeNode* pr = new TreeNode();
p->right = pr;
build(pr,(l+r)/2+1,r);
}
}
TreeNode* balanceBST(TreeNode* root)
{
go(root);
TreeNode* p = new TreeNode();
int len = paper.size();
if(len == 0)return NULL;
build(p,0,len-1);
return p;
}
};
```