首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

创建一个接受平面数组并转换为树数据结构的递归函数

,可以使用以下方式实现:

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def array_to_tree(nums):
    if not nums:
        return None

    # 递归函数,将平面数组转换为树
    def build_tree(left, right):
        if left > right:
            return None

        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = build_tree(left, mid - 1)
        node.right = build_tree(mid + 1, right)
        return node

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

这个函数接受一个平面数组 nums,并返回一个树的根节点。函数内部使用递归的方式将平面数组转换为树。具体实现如下:

  1. 首先定义了一个 TreeNode 类,表示树的节点。每个节点包含一个值 val,以及左右子节点 leftright
  2. array_to_tree 函数中,首先判断输入的数组是否为空,如果为空则直接返回 None
  3. 在内部定义了一个递归函数 build_tree,该函数接受左右边界 leftright,表示当前处理的数组范围。
  4. 在递归函数中,首先判断左边界是否大于右边界,如果是则返回 None,表示当前范围为空。
  5. 计算当前范围的中间位置 mid,将 nums[mid] 的值作为当前节点的值创建一个新的节点 node
  6. 递归调用 build_tree 函数,将左边界到 mid-1 的范围作为左子树,将 mid+1 到右边界的范围作为右子树,分别赋值给 node.leftnode.right
  7. 最后返回根节点 node
  8. 在外部调用 build_tree 函数,传入初始范围为整个数组的左右边界,返回树的根节点。

这个函数的时间复杂度为 O(n),其中 n 是数组的长度。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券