Description
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
问题分析
每次取数组的中间元素作为当前节点即可
解法
public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if(nums == null || nums.length == 0) return null; return getTreeNode(nums, 0, nums.length - 1); } private TreeNode getTreeNode(int[] nums, int start, int end){ //注意这里 if(start > end) return null; //取中间元素作为当前节点 int middle = start + (end - start) / 2; TreeNode n = new TreeNode(nums[middle]); //注意start和end的变化 n.left = getTreeNode(nums, start, middle - 1); n.right = getTreeNode(nums, middle + 1, end); return n; } }