題目介紹
描述：
將一個(gè)按照升序排列的有序數(shù)組攀芯，轉(zhuǎn)換為一棵高度平衡二叉搜索樹别凹。
本題中糊肠，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1轻纪。
示例:
給定有序數(shù)組: [-10,-3,0,5,9],
一個(gè)可能的答案是：[0,-3,9,-10,null,5]侨把，它可以表示下面這個(gè)高度平衡二叉搜索樹：
0
/ \\
-3 9
/ /
-10 5
解題思路：
遞歸算法的關(guān)鍵是要明確函數(shù)的「定義」是什么谆焊，然后相信這個(gè)定義厚掷，利用這個(gè)定義推導(dǎo)最終結(jié)果绿聘。
寫樹相關(guān)的算法室埋，簡(jiǎn)單說就是办绝，先搞清楚當(dāng)前 root 節(jié)點(diǎn)該做什么伊约，然后根據(jù)函數(shù)定義遞歸調(diào)用子節(jié)點(diǎn)，遞歸調(diào)用會(huì)讓孩子節(jié)點(diǎn)做相同的事情孕蝉。
二叉樹題目的一個(gè)難點(diǎn)在于如何通過題目的要求思考出每一個(gè)節(jié)點(diǎn)需要做什么
自己的解法實(shí)現(xiàn)
def sortedArrayToBST(self, nums):
if not nums: return None
mid = (len(nums) - 1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
網(wǎng)上比較優(yōu)秀的解法
解法一
二叉搜索樹的中序遍歷是升序序列屡律，題目給定的數(shù)組是按照升序排序的有序數(shù)組，因此可以確保數(shù)組是二叉搜索樹的中序遍歷序列降淮。
def sortedArrayToBST(self, nums):
if not nums: return None
def helper(left, right):
if left > right: return None
# 總是選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)
mid = (left + right )//2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)
解法二
二叉搜索樹的特性：二叉搜索樹的中序遍歷結(jié)果為遞增序列超埋。
中序遍歷的順序?yàn)椋鹤蠊?jié)點(diǎn) → 根節(jié)點(diǎn) → 右節(jié)點(diǎn)。這個(gè)遍歷過程可以使用遞歸非常直觀地進(jìn)行表示佳鳖。
如何構(gòu)造樹： 構(gòu)造一棵樹的過程可以拆分成無(wú)數(shù)個(gè)這樣的子問題：構(gòu)造樹的每個(gè)節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系霍殴。對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說，都需要：
- 選取節(jié)點(diǎn)
- 構(gòu)造該節(jié)點(diǎn)的左子樹
- 構(gòu)造該節(jié)點(diǎn)的右子樹 因題目要求構(gòu)造一棵「高度平衡」的樹系吩，所以我們?cè)谶x取節(jié)點(diǎn)時(shí)選擇數(shù)組的中點(diǎn)作為根節(jié)點(diǎn)来庭，以此來(lái)保證平衡性。
def sortedArrayToBST2(self, nums):
if not nums: return None
# 找到中點(diǎn)作為根節(jié)點(diǎn)
mid = len(nums)//2
node = TreeNode(nums[mid])
# 左側(cè)數(shù)組作為左子樹
left = nums[:mid]
# 右側(cè)數(shù)字作為右子樹
right = nums[mid + 1:]
# 遞歸調(diào)用
node.left = self.sortedArrayToBST2(left)
node.right = self.sortedArrayToBST2(right)
return node
相關(guān)知識(shí)總結(jié)和思考
相關(guān)知識(shí)：
BFS：廣度/寬度優(yōu)先穿挨。其實(shí)就是從上到下月弛，先把每一層遍歷完之后再遍歷一下一層。
可以使用Queue的數(shù)據(jù)結(jié)構(gòu)科盛。我們將root節(jié)點(diǎn)初始化進(jìn)隊(duì)列帽衙，通過消耗尾部，插入頭部的方式來(lái)完成BFS土涝。
二叉搜索樹（BST）的特性：
- 若它的左子樹不為空佛寿，則所有左子樹上的值均小于其根節(jié)點(diǎn)的值
- 若它的右子樹不為空，則所有右子樹上的值均大于其根節(jié)點(diǎn)的值
- 它的左右子樹也分別為二叉搜索樹
遞歸與迭代的區(qū)別
遞歸：重復(fù)調(diào)用函數(shù)自身實(shí)現(xiàn)循環(huán)稱為遞歸但壮； 迭代：利用變量的原值推出新值稱為迭代冀泻，或者說迭代是函數(shù)內(nèi)某段代碼實(shí)現(xiàn)循環(huán)；
AVL樹是一種高度平衡的(height balanced)二叉搜索樹：對(duì)每一個(gè)結(jié)點(diǎn)x蜡饵，x的左子樹與右子樹的高度差(平衡因子)至多為1弹渔。
