网站建设设计文档模板下载html简单网页代码

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 

平衡二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解题思路＋代码：

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode sortedArrayToBST(int[] nums) {/**思路：BST(深度优先搜索中的中序遍历--左根右)1.判断数组的左右边界，左边界大于右边界时返回null2.创建BST方法找到数组的中点3.由于数组是升序数组，直接按照二分搜索（小于中点在左子树，大于中点在右子树）的方式来存放到二叉树中*///这里右边界需要注意数组范围溢出return BST(nums,0,nums.length-1);}public TreeNode BST(int[] nums,int left,int right){//数组的左边和右边，升序数组不存在左边大于右边的情况if(left > right){return null;}//求数组的中点int mid = (left + right) / 2;//new一个root对象作为根节点TreeNode root = new TreeNode(nums[mid]);//存放树的叶节点  root的左边放小于中点的数 root的右边放大于中点的数 root.left = BST(nums,left,mid - 1);root.right = BST(nums,mid + 1,right);return root;}
}

总结：解答这道题需要了解数组和搜索二叉树的相关性质。数组转换成搜索二叉树，可以联想到二分查找法，那么首先需要找到数组（题目所给是升序数组，否则需排序）的中点，左右边界相加除以2找到数组中点，中点左边为比中点小的数，右边为比中点大的数。搜索二叉树即为平衡二叉树（BST），可以使用深度优先搜索方法中的中序遍历（左根右），根节点为中点，左子树为比根节点小的数，右边为比根节点大的数。此时，二分查找的数组与平衡二叉树就极为相似，最后只需要将数组遍历后存放到平衡二叉树当中就完成了转换。