构建二叉查找树，一不小心平衡将有序数组转换为二叉查找树题目链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree将按升序排序的数组转换为高度平衡的二叉搜索树。本题中，高度平衡的二叉树是指一棵二叉树的每个节点的左右子树的高度差的绝对值不超过1。例子：思路在做这道题之前，你可以先了解这几点:由中序和后序遍历序列构造一棵二叉树最大二叉树二叉搜索树中的插入操作删除二叉搜索树中的节点进入正题：题目说到转换为高度平衡的二叉树搜索树。这和转换成普通的二叉搜索树有什么区别？其实平衡二叉查找树这里不用特别强调。用数组构造二叉树是很自然的，形成平衡树也是自然的，因为大家默认都是从数组中间取值，因为Node元素一般不会随机选取，所以如果要形成一棵不平衡的二叉树，你是在自找麻烦。二叉树中：构造二叉树登场！而二叉树：构造最大的二叉树前面已经说过了，如果是根据数组构造二叉树的话。本质就是找到分裂点，分裂点就是当前节点，然后递归左右区间。这道题其实比BinaryTree:ConstructingaBinaryTree还要简单！和二叉树：构造最大的二叉树，因为从有序数组构造二叉搜索树时更容易找到分裂点。分割点是数组中间的节点。那么问题来了，如果数组的长度是偶数，中间有两个节点，选哪个呢？任选其一，但构成不同的平衡二叉搜索树。例如：输入：[-10,-3,0,5,9]下面两棵树是这个数组的平衡二叉查找树：将有序数组转换成二叉查找树如果要拆分的数组长度是偶数的时候，中间有两个元素，左边的元素是树1，右边的元素是树2。这就是为什么题目强调答案不是唯一的。明白了这一点，这个问题就很好理解了。递归与递归三部曲：确定递归函数的返回值及其参数。删除二叉树节点和添加二叉树节点。都是用递归函数的返回值来完成的，比较方便。相信如果你仔细阅读过二叉树：查找树中的插入操作和二叉树：查找树中的删除操作，一定会对递归函数返回值的作用印象深刻。那么这道题就是构造一棵二叉树，还是用递归函数的返回值构造中间节点的左右孩子。我们再看看参数。首先传入数组，然后是左下表left，右下表right。我们在二叉树：构造二叉树出道！中提到，在构造二叉树时尽量不要重新定义左右区间数组，而是使用下表操作原始数组。所以代码如下：//左闭右闭区间[left,right]TreeNode*traversal(vector&nums,intleft,intright)这里注意，我这里定义的是左闭右闭区间，在连续划分的过程中，也会坚持左闭区间和右闭区间，这又涉及到我们讲的循环不变量。数组：每次遇到二分法，第一眼就会看到，一写就舍弃；nj在二叉树中：Constructingabinarytreedebut!,704.Binarysearch和59.SpiralmatrixII详细讲了loopinvariants。确定递归终止条件。这里定义的区间是左闭和右闭的，所以当区间left>right时，为空节点。代码如下：if(left>right)returnnullptr;判断单级递归的逻辑，先取数组中间元素的位置，intmid=(left+right)/2;不难写，这样写其实有问题，即值越界，比如left和right都是最大的int，所以操作越界，尤其是二分法！所以你可以这样写：intmid=left+((right-left)/2);但是这道题的leetcode测试数据是不会越界的，所以可以随便写。但是你需要有这个意识！取中间位置后，开始以中间位置的元素构造节点，代码：TreeNode*root=newTreeNode(nums[mid]);。然后划分区间，root的左孩子抓下一层左区间的构造节点，右孩子抓下一层右区间构造的节点。最后返回根节点。单层递归整体代码如下：intmid=left+((right-left)/2);TreeNode*root=newTreeNode(nums[mid]);root->left=traversal(nums,left,mid-1);root->right=traversal(nums,mid+1,right);returnroot;其中intmid=left+((right-left)/2);相当于如果数组的长度是偶数，中间位置有两个元素，取左边那个。递归整体代码如下：classSolution{private:TreeNode*traversal(vector&nums,intleft,intright){if(left>right)returnnullptr;intmid=left+((right-left)/2);TreeNode*root=newTreeNode(nums[mid]);root->left=traversal(nums,left,mid-1);root->right=traversal(nums,mid+1,right);returnroot;}public:TreeNode*sortedArrayToBST(vector&nums){TreeNode*root=traversal(nums,0,nums.size()-1);returnroot;}};注意：调用遍历时，为什么左右为0，nums.size()-1，因为定义的区间是左闭和右闭的。迭代法迭代法可以通过三个队列来模拟，一个队列是遍历的节点，一个队列是左区间下面的表，一个队列是右区间下面的表。模拟的是连续分割的过程。C++代码如下：（我已经详细注释了）classSolution{public:TreeNode*sortedArrayToBST(vector&nums){if(nums.size()==0)returnnullptr;TreeNode*root=newTreeNode(0);//初始根节点queuenodeQue;//放置遍历节点queueleftQue;//保存左区间下方的表queuerightQue;//保存右区间下方的表nodeQue.push(root);//根节点入队leftQue.push(0);//0为左段下方表的初始位置rightQue.push(nums.size()-1);//nums.size()-1是表右段下方的初始位置while(!nodeQue.empty()){TreeNode*curNode=nodeQue.front();nodeQue.pop();intleft=leftQue.front();leftQue.pop();intright=rightQue.front();rightQue.pop();intmid=left+((right-left)/2);curNode->val=nums[mid];//给出对应的元素tomid到中间节点if(left<=mid-1){//处理左区间curNode->left=newTreeNode(0);nodeQue.push(curNode->left);leftQue.push(left);rightQue.push(mid-1);}if(right>=mid+1){//处理右区间curNode->right=newTreeNode(0);nodeQue.push(curNode->right);leftQue.push(mid+1);rightQue.push(right);}}returnroot;}};二叉树总结：二叉树的构建登场！而二叉树：构造完最大二叉树之后，自然要构造一颗二叉搜索树，一不小心还是平衡二叉搜索树。其实思路是一样的，中间继续划分，然后递归处理左区间和右区间，也可以说是分而治之。这时候相信大家应该对通过递归函数的返回值来增删二叉树不陌生了，这也是常规操作。在定义区间的过程中，我们再次强调了循环不变量的重要性。最后还是给出了迭代的方法，其实就是模拟中间元素，然后不断分裂构造二叉树的过程。Java其他语言版本的递归：left-closed-right-closed[left,right]classSolution{publicTreeNodesortedArrayToBST(int[]nums){TreeNoderoot=traversal(nums,0,nums.length-1);returnroot;}//left-closedright-closedinterval[left,right)privateTreeNodetraversal(int[]nums,intleft,intright){if(left>right)returnnull;intmid=left+((right-left)>>1);TreeNoderoot=newTreeNode(nums[mid]);root.left=traversal(nums,left,mid-1);root.right=traversal(nums,mid+1,right);returnroot;}}迭代：左闭右闭[left,right]classSolution{publicTreeNodesortedArrayToBST(int[]nums){if(nums.length==0)returnnull;//根节点初始化TreeNoderoot=newTreeNode(-1);QueuenodeQueue=newLinkedList<>();QueueleftQueue=newLinkedList<>();QueuerightQueue=newLinkedList<>();//根节点入队nodeQueue.offer(root);//0为左区间下方表的初始位置leftQueue.offer(0);//nums.size()-1是表在r下方的初始位置右间隔rightQueue.offer(nums.length-1);while(!nodeQueue.isEmpty()){TreeNodecurrNode=nodeQueue.poll();intleft=leftQueue.poll();intright=rightQueue.poll();intmid=left+(((right-left)>>1);//将mid对应的元素赋给中间节点currNode.val=nums[mid];//处理左区间if(left<=mid-1){currNode.left=newTreeNode(-1);nodeQueue.offer(currNode.left);leftQueue.offer(left);rightQueue.offer(mid-1);}//处理右区间if(right>=mid+1){currNode.right=newTreeNode(-1);nodeQueue.offer(currNode.right);leftQueue.offer(mid+1);rightQueue.offer(right);}}returnroot;}}Python递归方法：classSolution:defsortedArrayToBST(self,nums:List[int])->TreeNode:defbuildaTree(left,right):ifleft>right:returnNone#左闭右闭区间，当区间left>right时，为空节点，当left=right时，它不为空mid=left+(right-left)//2#保证数据不会越界val=nums[mid]root=TreeNode(val)root.left=buildaTree(left,mid-1)root.right=buildaTree(mid+1,right)returnrootroot=buildaTree(0,len(nums)-1)#左闭右闭区间returnroot。
