LeetCode-109-有序鏈表轉(zhuǎn)換二叉搜索樹
本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò) 1。
示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。
來(lái)源：力扣（LeetCode） ??
鏈接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/ ??
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
解法一：遞歸
首先，將鏈表轉(zhuǎn)化成數(shù)組，然后處理過(guò)程就和 LeetCode-108-將有序數(shù)組轉(zhuǎn)換為二叉搜索樹 的解法完全一樣了。
根據(jù)二叉搜索樹的性質(zhì)，因?yàn)榻o定的數(shù)組是按升序排列的，所以可以確定數(shù)組num即為該二叉搜索樹的中序遍歷序列，為了得到一顆平衡的二叉樹，取數(shù)組中間位置的節(jié)點(diǎn)作為根節(jié)點(diǎn)，這樣，左右子樹的節(jié)點(diǎn)較為平衡，具體處理過(guò)程如下：
調(diào)用遞歸方法，初始的起始位置為數(shù)組的長(zhǎng)度；
當(dāng)起點(diǎn)位置大于終點(diǎn)位置時(shí)，說(shuō)明節(jié)點(diǎn)已經(jīng)遍歷完了，直接返回空樹；
獲取中間位置的值作為根節(jié)點(diǎn)，這樣左右子樹的節(jié)點(diǎn)樹是比較均衡的；
然后遞歸獲得當(dāng)前根節(jié)點(diǎn)的左右子樹；
最后返回根節(jié)點(diǎn)即為平衡的二叉搜索樹。
【每日寄語(yǔ)】 任鐵任金，定有可穿之硯；日磨日削，從無(wú)不銳之針。
