一樟结、題目
給你一個(gè)整數(shù)數(shù)組 nums 养交，其中元素已經(jīng)按 升序 排列，請(qǐng)你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹(shù)瓢宦。
高度平衡 二叉樹(shù)是一棵滿(mǎn)足「每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 」的二叉樹(shù)碎连。
二、示例
2.1> 示例 1：
【輸入】nums = [-10,-3,0,5,9]
【輸出】[0,-3,9,-10,null,5]
【解釋】[0,-10,5,null,-3,null,9] 也將被視為正確答案：
2.2> 示例 2：
【輸入】nums = [1,3]
【輸出】[3,1]
【解釋】[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹(shù)驮履。
提示：
-
1<= nums.length <=10^4 -
-10^4<= nums[i] <=10^4 -
nums按 嚴(yán)格遞增 順序排列
三鱼辙、解題思路
根據(jù)題目要求，我們要根據(jù)題目給出的nums數(shù)組玫镐，將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹(shù)倒戏。那么我們就要保障根節(jié)點(diǎn)的左子樹(shù)節(jié)點(diǎn)總數(shù)與右子樹(shù)節(jié)點(diǎn)總數(shù)之差不要超過(guò)1。
首先恐似，我們要獲得中心節(jié)點(diǎn)mid杜跷，有如下兩種獲取方式：
【方式1】通過(guò)
數(shù)組長(zhǎng)度除以2獲得中心點(diǎn)mid—— nums.length / 2；
【方式2】通過(guò)雙指針除以2獲得中心點(diǎn)mid—— (start + end) / 2;
然后，我們創(chuàng)建min值對(duì)應(yīng)的TreeNode葛闷，即：new TreeNode(nums[mid]); 由于我希望減少數(shù)組切割的性能消耗憋槐，所以采用雙指針的方式進(jìn)行“數(shù)組拆分”操作。那么尋找中心點(diǎn)mid也就自然而然的采用“方式2”了淑趾。此時(shí)阳仔，將原有數(shù)組拆分為兩部分，分別為[start, mid-1]和[mid+1, end]扣泊，然后再分別針對(duì)這兩部分?jǐn)?shù)組再次執(zhí)行上面操作即可近范。
通過(guò)以上的解題思路，我們?cè)诰幋a時(shí)旷赖，就可以通過(guò)遞歸調(diào)用方式進(jìn)行解題了顺又。為了便于大家理解更卒，下面我們以輸入nums = [-10,-3,0,5,9]為例等孵，看一下具體的解題過(guò)程。請(qǐng)見(jiàn)下圖所示：
四蹂空、代碼實(shí)現(xiàn)
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sort(nums, 0, nums.length - 1);
}
public TreeNode sort(int[] nums, int start, int end) {
if (start > end) return null;
int mid = (start + end) / 2; // nums數(shù)組的尋找中心點(diǎn)
TreeNode node = new TreeNode(nums[mid]);
node.left = sort(nums, start, mid - 1); // 獲得node的左節(jié)點(diǎn)
node.right = sort(nums, mid + 1, end); // 獲得node的右節(jié)點(diǎn)
return node;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
今天的文章內(nèi)容就這些了：
寫(xiě)作不易俯萌，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來(lái)您幾秒鐘的 點(diǎn)贊 & 分享 上枕。
更多技術(shù)干貨咐熙，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(o)/ ~ 「干貨分享，每天更新」
