題目

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

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

解題思路

1. 可以采用二分法，每次選數(shù)組中間值為根節(jié)點(diǎn)創(chuàng)建樹，這樣可以確保左右子樹的高度差的絕對(duì)值不超過1；
2. 通過遞歸來逐級(jí)生成后續(xù)節(jié)點(diǎn)；
3. 可通過變量設(shè)置左右邊界，方便后續(xù)節(jié)點(diǎn)區(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));}
}