一、題目

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

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

二、示例

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] 都是高度平衡二叉搜索樹。

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 按 嚴(yán)格遞增 順序排列

三、解題思路

根據(jù)題目要求，我們要根據(jù)題目給出的nums數(shù)組，將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。那么我們就要保障根節(jié)點(diǎn)的左子樹節(jié)點(diǎn)總數(shù)與右子樹節(jié)點(diǎn)總數(shù)之差不要超過1。

首先，我們要獲得中心節(jié)點(diǎn)mid，有如下兩種獲取方式：

【方式1】通過數(shù)組長(zhǎng)度除以2獲得中心點(diǎn)mid—— nums.length / 2；
【方式2】通過雙指針除以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í)行上面操作即可。

通過以上的解題思路，我們?cè)诰幋a時(shí)，就可以通過遞歸調(diào)用方式進(jìn)行解題了。為了便于大家理解，下面我們以輸入nums = [-10,-3,0,5,9]為例，看一下具體的解題過程。請(qǐng)見下圖所示：

四、代碼實(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)容就這些了：

寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 。

更多技術(shù)干貨，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(^o)/ ~ 「干貨分享，每天更新」