題目

給你一個整數(shù)數(shù)組?nums?，其中元素已經(jīng)按?升序?排列，請你將其轉(zhuǎn)換為一棵?高度平衡?二叉搜索樹。

高度平衡?二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

解題思路

1. 可以采用二分法，每次選數(shù)組中間值為根節(jié)點創(chuàng)建樹，這樣可以確保左右子樹的高度差的絕對值不超過1；
2. 通過遞歸來逐級生成后續(xù)節(jié)點；
3. 可通過變量設(shè)置左右邊界，方便后續(xù)節(jié)點區(qū)間的取值；

代碼展示

class Solution {public TreeNode sortedArrayToBST(int[] nums) {TreeNode data = toBST(nums, 0, nums.length - 1);return data;}public TreeNode toBST(int[] nums, int left, int right){if(left > right){return null;}int middle = (left + right) / 2;return new TreeNode(nums[middle], toBST(nums, left, middle - 1), toBST(nums, middle + 1, right));}
}