LC108-将有序数组转化为二叉搜索树（二叉平衡树）

1 题目

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡二叉搜索树

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

2 思路

构造平衡二叉树？岂不是在不平衡的时候还需要左旋和右旋，这是对于一般的数组构建二叉平衡树来说的：就是当不满足任意一个左右子树高度之差的绝对值小于等于1的时候，需要进行旋转来保持二叉树的平衡。

但是这是一个排序好的数组，想一想，取中间的元素作为根元素，其余元素作为子树来构建二叉树，不是刚刚能达到平衡的条件吗？因为左右子树的个数都是一样的，如果还继续这样构造下去，一定能满足平衡的条件；想一想三个节点的情况，[1, 2, 3] 使用2作为根节点来构造

因此对于排序好的数组构建二叉平衡树，直接取中间元素作为根元素即可

注意：
对于奇数个元素还是偶数个元素取mid的问题，如果是奇数个，刚好能取到中间；如果是偶数个，则取中间两个的后一个；如果取前一个，都是正确的，所以才导致答案不唯一；
如何取mid？int mid = (left+right)/2;还是int mid = left + (right - left)/2; 其实第一种有溢出的风险，如果left和right都是Integer.MAX_VALUE就直接溢出了，计算结果错误，因此使用第二种更加合理

Code：

class Solution{public TreeNode sortedArrayToBST(int[] nums) {if (nums.length == 0) return null;int left = 0, right = nums.length - 1;TreeNode root = arrayToBST(nums, left, right);return root;}private TreeNode arrayToBST(int[] nums, int left, int right) {// 递归结束if (left > right) {return null;}int mid = left + ((right - left) / 2);    // 寻找中点防溢出计算TreeNode root = new TreeNode(nums[mid]);root.left = arrayToBST(nums, left, mid - 1);root.right = arrayToBST(nums, mid+1, right);return root;}

3 ACM完整代码

import java.util.*;class TreeNode{int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val; }}// Solutionpublic class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = in.nextInt();}Solution solution = new Solution();TreeNode node = solution.sortedArrayToBST(nums);preOrderTree(node);}static void preOrderTree(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preOrderTree(root.left);preOrderTree(root.right);}}}
/*
test case:
5
-10 -3 0 5 9*/

参考

https://www.programmercarl.com/0108.将有序数组转换为二叉搜索树.html