LeetCode-108-將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
難度簡單
給你一個整數(shù)數(shù)組 nums 实蔽，其中元素已經(jīng)按 升序 排列，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹谨读。
高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹局装。
示例 1：
img
輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：
示例 2：
img
輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,3] 和 [3,1] 都是高度平衡二叉搜索樹。
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104-
nums按 嚴格遞增 順序排列
題解
BST的中序遍歷是升序的劳殖，因此本題等同于根據(jù)中序遍歷的序列恢復二叉搜索樹铐尚。因此我們可以以升序序列中的任一個元素作為根節(jié)點，以該元素左邊的升序序列構(gòu)建左子樹哆姻，以該元素右邊的升序序列構(gòu)建右子樹宣增，這樣得到的樹就是一棵二叉搜索樹啦～ 又因為本題要求高度平衡，因此我們需要選擇升序序列的中間元素作為根節(jié)點奧
遞歸中間元素作為節(jié)點：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return process(nums, 0, nums.length - 1);
}
public static TreeNode process(int[] nums, int L, int R) {
if (L > R) {
return null;
}
if (L == R) {
return new TreeNode(nums[L]);
}
int M = (L + R) / 2;
TreeNode head = new TreeNode(nums[M]);
head.left = process(nums, L, M - 1);
head.right = process(nums, M + 1, R);
return head;
}
}
image-20210608085532594
