网站查询备案信息青岛中小企业网站制作

网站查询备案信息,青岛中小企业网站制作,网站编程培训班,企业如何在工商网站上做公示【LetMeFly】1382.将二叉搜索树变平衡#xff1a;分治——求得所有节点再重新建树 力扣题目链接#xff1a;https://leetcode.cn/problems/balance-a-binary-search-tree/ 给你一棵二叉搜索树#xff0c;请你返回一棵 平衡后 的二叉搜索树#xff0c;新生成的树应该与原来…【LetMeFly】1382.将二叉搜索树变平衡分治——求得所有节点再重新建树力扣题目链接https://leetcode.cn/problems/balance-a-binary-search-tree/给你一棵二叉搜索树请你返回一棵平衡后的二叉搜索树新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法请你返回任意一种。如果一棵二叉搜索树中每个节点的两棵子树高度差不超过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, 104]范围内。1 Node.val 105解题方法分治题目给定的二叉搜索树有何特征二叉搜索树的中序遍历结果是有序的。平衡二叉树有何特征任一节点左右子树高度差不超过1 11一个有序节点数组如何建成平衡二叉树取数组中点作为根节点中点左边数组作为左子树中点右边节点作为右子树递归建树。Over。时间复杂度O ( s i z e ( t r e e ) ) O(size(tree))O(size(tree))空间复杂度O ( s i z e ( t r e e ) ) O(size(tree))O(size(tree))AC代码C/* * LastEditTime: 2026-02-09 23:21:12 *//* 1 2 3 4 5 6 7 8 9 5 2 7 1 3 6 8 4 9 */classSolution{private:vectorTreeNode*nodes;voiddfs(TreeNode*node){if(!node){return;}dfs(node-left);nodes.push_back(node);dfs(node-right);}TreeNode*build(intl,intr){if(lr){returnnullptr;}intmid(lr)1;TreeNode*rootnodes[mid];root-leftbuild(l,mid);root-rightbuild(mid1,r);returnroot;}public:TreeNode*balanceBST(TreeNode*root){dfs(root);returnbuild(0,nodes.size());}};#ifdefined(_WIN32)||defined(__APPLE__)/* [1,null,2,null,3,null,4] */intmain(){string s;while(cins){TreeNode*rootstringToTree(s);coutoriginal tree: rootendl;Solution sol;rootsol.balanceBST(root);deleteTree(root);}return0;}#endif同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源