# [LeetCode]第十九题 ：有序数组转换成平衡二叉树

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

``````Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5``````

1.我的解法：其实想法很简单，平衡二叉树，其左子树的值都小于根节点，右子树的值都大于根节点。那么从数组的中间取值作为根节点，左子树是从数组的0到中间位置 – 1，右子树是从中间位置 + 1到末尾，然后递归生成左右子树即可。代码如下：

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0) return null;
int index = nums.length / 2;
TreeNode node = new TreeNode(nums[index]);
int[] leftArray = new int[index];
for(int i = 0;i<leftArray.length;i++) {
leftArray[i] = nums[i];
}
node.left = sortedArrayToBST(leftArray);
int[] rightArray = new int[nums.length - index - 1];
for(int i = 0;i<rightArray.length;i++) {
rightArray[i] = nums[index + 1 + i];
}
node.right = sortedArrayToBST(rightArray);
return node;
}
}``````

原文作者：平衡二叉树
原文地址: https://blog.csdn.net/woaily1346/article/details/80927278
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。