思路
两个要点：
二叉搜索树。每个节点的左右两个子树的高度差都不超过 1 。
因为给定数组是有序的，那我们很容易就能找到适合做 root 的值，即数组最中间的那个值。 这样把数组分成了左、右两部分， root 的左节点就是左边数组中最中间的那个值， root的右节点就是右边数组中最中间的那个值。
递归，直到
数组长度为 0 时，返回 null。数组长度为 1 时，返回唯一值构成的节点。
最后返回 root。
复杂度分析
假设树有 n 个节点。
时间复杂度O(n)，遍历整棵树。空间复杂度O(n)，空间复杂度取决二叉树的节点数。
代码
public static TreeNode
sortedArrayToBST(int[] nums
) {
return sortedArrayToBST(nums
, 0, nums
.length
- 1);
}
private static TreeNode
sortedArrayToBST(int[] nums
, int left
, int right
) {
if (right
< left
) {
return null
;
}
if (right
== left
) {
return new TreeNode(nums
[left
]);
}
int middle
= (left
+ right
) / 2;
TreeNode root
= new TreeNode(nums
[middle
]);
root
.left
= sortedArrayToBST(nums
, left
, middle
- 1);
root
.right
= sortedArrayToBST(nums
, middle
+ 1, right
);
return root
;
}
