将升序数组转化为平衡二叉搜索树

问题简述

给定升序数组，转化为平衡二叉搜索树（BST）

将升序数组转化为平衡二叉搜索树_牛客题霸_牛客网

思路

• 每次选择中间节点作为根节点，按先序遍历递归构建 BST；

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return TreeNode类
#
class Solution:
    def sortedArrayToBST(self , num: List[int]) -> TreeNode:
        # write code here
        def dfs(arr):
            if not arr: return None
            
            l, r = 0, len(arr) - 1
            mid = (l + r) // 2
            
            node = TreeNode(arr[mid])
            node.left = dfs(arr[:mid])
            node.right = dfs(arr[mid + 1:])
            
            return node
        
        return dfs(num)