leetcode 108 有序数组转平衡二叉树

这个题乍一看真的没什么思路因为平衡二叉树自古以来就是老大难问题如何建立的时候就平衡这需要一些贪心的思想。这个题目的官方题解写的非常好这个题其实是一个不断二分的过程每次找中间节点左边的分到左子树右边的分到右子树一致这样递归二分下去即可。但是如果一直是奇数节点还好说如果出现偶数节点呢我们应该选择左边还是右边的节点这个就是一种贪心思想答案是怎么选都无所谓都可以让这棵树尽可能的平衡。/** * 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) {} * }; */typedefvectorintV;classSolution{public:TreeNode*dfs(Vnums,intl,intr){if(lr)returnnullptr;intmidl(r-l)/2;TreeNode*nnewTreeNode(nums[mid]);n-leftdfs(nums,l,mid-1);n-rightdfs(nums,mid1,r);returnn;}TreeNode*sortedArrayToBST(vectorintnums){intnnums.size();intmid0(n-1)/2;TreeNode*rootnewTreeNode(nums[mid]);root-leftdfs(nums,0,mid-1);root-rightdfs(nums,mid1,n-1);returnroot;}};