Leetcode 1382. Balance a Binary Search Tree (python+cpp)

题目

解法：

• inorder得到排序数组
• divide and conquer简历平衡二叉搜索树

class Solution:def balanceBST(self, root: TreeNode) -> TreeNode:def inorder(node):if not node:return inorder(node.left)order.append(node)inorder(node.right)def buildTree(curr_order):if not curr_order:return Nonemid = len(curr_order)//2root = curr_order[mid]root.left = buildTree(curr_order[:mid])root.right = buildTree(curr_order[mid+1:])return rootorder = []inorder(root)return buildTree(order)

C++版本

class Solution {
    vector<TreeNode*> order;
public:TreeNode* balanceBST(TreeNode* root) {
    inorder(root,order);return buildTree(0,order.size()-1);}void inorder(TreeNode* node, vector<TreeNode*>& order){
    if (node == nullptr) return;inorder(node->left,order);order.push_back(node);inorder(node->right,order);}TreeNode* buildTree(int start,int end){
    if (start>end) return NULL;int mid = (start+end)/2;TreeNode* root = order[mid];root->left = buildTree(start,mid-1);root->right = buildTree(mid+1,end);return root;}
};