Python教程：將有序數組轉換為二叉搜索樹

題目：

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

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

示例:

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




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



      
0

     
/ 
\

   
-3   
9

   
/   
/

 
-10  
5

解題思路

思路：遞歸

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

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

在這里，可以看到有序數組是按照升序排序的。我們知道，二叉搜索樹（BST）中序遍歷就是升序序列，那么我們可以從這個角度出發，那么問題就轉變為 從中序遍歷的序列中恢復二叉搜索樹。

那么任選一個元素作為根節點，以元素左邊的序列構建左子樹，右邊序列構建右子樹。

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

具體的實現代碼如下。

代碼實現

# 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

            

            # 選取中間元素為根節點

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




            root = TreeNode(nums[mid])


            # 中間元素左邊序列構建左子樹


            # 右邊序列構建右子樹


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


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




            return root


        


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

實現結果

總結

• 題目中提示，有序數組是按照升序排序的，要將其轉換為高度平衡的二叉搜索樹。因為數組按照升序排序，而 BST 中序遍歷的序列是升序序列。那么題目所求可變為求中序遍歷序列轉換為高度平衡二叉搜索樹。

• 因為題目要求轉換為高度平衡二叉搜索樹，那么在數組中，應該取中間元素作為根節點。中間元素左邊序列構建左子樹，右邊序列構建右子樹。