用Python实现数组转成完全二叉搜索树

可以使用递归的方式，具体实现如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    if not nums:
        return None
    
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    
    return root

首先判断数组是否为空，如果为空则返回 None。否则，找到数组的中间位置，将该位置的值作为根节点，递归处理左右子树，最后返回根节点。由于数组是有序的，因此可以保证转化成的二叉搜索树是平衡的。

相关问题

用python把二叉搜索树转换成循环的双链表

可以使用中序遍历二叉树的方式，将其转换为有序的列表，然后将列表中的元素依次连接成双向链表即可。

以下是代码实现：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bst_to_dll(root):
    # 中序遍历二叉树，将节点值存入数组
    def inorder(root):
        if not root:
            return []
        return inorder(root.left) + [root] + inorder(root.right)

    # 将有序数组转换为双向链表
    def to_dll(arr):
        n = len(arr)
        for i in range(n):
            arr[i].left = arr[i-1]
            arr[i].right = arr[(i+1)%n]
        return arr[0]

    # 主函数
    if not root:
        return None
    arr = inorder(root)
    return to_dll(arr)

其中，`Node` 类表示二叉树节点，`bst_to_dll` 函数接受根节点 `root`，返回转换后的双向链表的头节点。

可以使用以下代码进行测试：

root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)

head = bst_to_dll(root)
node = head
for i in range(5):
    print(node.val)
    node = node.right

输出结果为：

1
2
3
4
5

最优二叉搜索树代码

以下是最优二叉搜索树的代码实现，使用动态规划算法：

def optimal_bst(keys, freq):
    n = len(keys)
    dp = [[0 for _ in range(n)] for _ in range(n)]
    cost = [freq[i] for i in range(n)]

    for i in range(n):
        dp[i][i] = cost[i]

    for L in range(2, n+1):
        for i in range(n-L+1):
            j = i + L - 1
            dp[i][j] = float('inf')
            for k in range(i, j+1):
                c = dp[i][k-1] + dp[k+1][j]
                if c < dp[i][j]:
                    dp[i][j] = c
                    cost[k] += sum(freq[i:j+1]) - freq[k]

    return dp[0][n-1]

其中，`keys` 是关键字数组，`freq` 是对应的频率数组。函数返回最优二叉搜索树的代价。