给你一棵二叉搜索树请你返回一棵平衡后的二叉搜索树新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法请你返回任意一种。如果一棵二叉搜索树中每个节点的两棵子树高度差不超过1我们就称这棵二叉搜索树是平衡的。示例 1输入root [1,null,2,null,3,null,4,null,null]输出[2,1,3,null,null,null,4]解释这不是唯一的正确答案[3,1,4,null,2,null,null] 也是一个可行的构造方案。示例 2输入:root [2,1,3]输出:[2,1,3]提示树节点的数目在[1, 10^4]范围内。1 Node.val 10^5分析先对原来的二叉搜索树进行中序遍历得到递增序列。之后令中点作为新平衡树的根再递归地建立根的左、右子树。/** * 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: void inorder(TreeNode* node,vectorintval) { if(node-left!NULL)inorder(node-left,val); val.push_back(node-val); if(node-right!NULL)inorder(node-right,val); } TreeNode* build(vectorintval,int l,int r) { if(lr)return NULL; int mid(lr)/2; TreeNode *p(TreeNode*)malloc(sizeof(TreeNode)); p-valval[mid];p-leftbuild(val,l,mid);p-rightbuild(val,mid1,r); return p; } TreeNode* balanceBST(TreeNode* root) { vectorintval; inorder(root,val); int nval.size(); TreeNode *root_newbuild(val,0,n); return root_new; } };