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

題目：

將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。

示例:

給定有序數(shù)組: 
[-10,-3,0,5,9],




一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：



      
0

     
/ 
\

   
-3   
9

   
/   
/

 
-10  
5

解題思路

思路：遞歸

先看題目所給出的要求以及限制。

• 將按照升序排列的有序數(shù)組，轉(zhuǎn)換為一顆高度平衡二叉搜索樹
• 高度平衡二叉樹：指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。

在這里，可以看到有序數(shù)組是按照升序排序的。我們知道，二叉搜索樹（BST）中序遍歷就是升序序列，那么我們可以從這個角度出發(fā)，那么問題就轉(zhuǎn)變?yōu)?從中序遍歷的序列中恢復(fù)二叉搜索樹。

那么任選一個元素作為根節(jié)點，以元素左邊的序列構(gòu)建左子樹，右邊序列構(gòu)建右子樹。

但是由于有限制條件，需要轉(zhuǎn)換為高度平衡二叉樹，根據(jù)前面給出高度平衡二叉樹的概念。那么我們考慮選擇數(shù)組的中間元素作為根節(jié)點來代替前面的任意選擇一個元素。

具體的實現(xiàn)代碼如下。

代碼實現(xiàn)

# Definition 
for a binary tree node.

# class TreeNode:

#     def __init__(
self, x):

#         
self.val = x

#         
self.left = 
None

#         
self.right = None



class Solution:

    def sortedArrayToBST(
self, nums: List[int]) -> TreeNode:

        def dfs(left, right):

            
if left > right:

                # 表示空子樹

                
return 
None

            

            # 選取中間元素為根節(jié)點

            mid = left + (right-left) 
// 2




            root = TreeNode(nums[mid])


            # 中間元素左邊序列構(gòu)建左子樹


            # 右邊序列構(gòu)建右子樹


            root.left = dfs(left, mid-1)


            root.right = dfs(mid+1, right)




            return root


        


        return dfs(0, len(nums)-1)

實現(xiàn)結(jié)果

總結(jié)

• 題目中提示，有序數(shù)組是按照升序排序的，要將其轉(zhuǎn)換為高度平衡的二叉搜索樹。因為數(shù)組按照升序排序，而 BST 中序遍歷的序列是升序序列。那么題目所求可變?yōu)榍笾行虮闅v序列轉(zhuǎn)換為高度平衡二叉搜索樹。

• 因為題目要求轉(zhuǎn)換為高度平衡二叉搜索樹，那么在數(shù)組中，應(yīng)該取中間元素作為根節(jié)點。中間元素左邊序列構(gòu)建左子樹，右邊序列構(gòu)建右子樹。