看了一眼提示,首先将二叉搜索树有序保存到vector中,然后再从vector中恢复为平衡搜索二叉树。
/**
* 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), right(right) {}
* };
*/
class Solution {
public:
TreeNode* balanceBST(TreeNode* root) {
vector<int> nums;
generate_vector(root,nums);
return generate_BST(nums,0,nums.size() - 1);
}
private:
TreeNode* generate_BST(const vector<int> &nums,int start,int end) {
if(start > end) return nullptr;
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = generate_BST(nums,start,mid - 1);
root->right = generate_BST(nums,mid + 1,end);
return root;
}
void generate_vector(TreeNode* root,vector<int> &nums) {
if(root == nullptr) return;
generate_vector(root->left,nums);
nums.push_back(root->val);
generate_vector(root->right,nums);
}
};
运行性能:
Runtime: 136 ms, faster than 73.84% of C++ online submissions for Balance a Binary Search Tree.
Memory Usage: 63.1 MB, less than 62.05% of C++ online submissions for Balance a Binary Search Tree.