將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

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

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

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸

根據(jù)二叉搜索樹的性質(zhì)，因為給定的數(shù)組是按升序排列的，所以可以確定數(shù)組num即為該二叉搜索樹的中序遍歷序列，為了得到一顆平衡的二叉樹，取數(shù)組中間位置的節(jié)點作為根節(jié)點，這樣，左右子樹的節(jié)點較為平衡，具體處理過程如下：

• 調(diào)用遞歸方法，初始的起始位置為數(shù)組的長度；

• 當起點位置大于終點位置時，說明節(jié)點已經(jīng)遍歷完了，直接返回空樹；

• 獲取中間位置的值作為根節(jié)點，這樣左右子樹的節(jié)點樹是比較均衡的；

• 然后遞歸獲得當前根節(jié)點的左右子樹；

• 最后返回根節(jié)點即為平衡的二叉搜索樹。

【每日寄語】 不辜負每個朝陽，不荒廢每個深夜，因平凡而奮斗，因奮斗而不平凡。