※ 引述 《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;
}
};
```