Python 中怎么将列表转化为二叉树

Day46: 列表转化为二叉树

已知列表nums，将其转化为二叉树。举例：

nums = [3,9,20,None,None,15,7]，转化为二叉树后:

节点3的左子节点9，右子节点20，9的左右子节点都为None，20的左子节点15，右子节点7，参考下面：

二叉树定义：

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

请补全下面函数：

def list_to_binarytree(nums):
    pass

构建分析

构建满足以上结构的二叉树，可以观察到：树的父节点和左右子节点的关系：

基于以上公式，再使用递归构建二叉树。

递归基情况：

if index >= len(nums) or nums[index] is None:
    return None

递归方程：

根据以上得到如下代码：

代码

def list_to_binarytree(nums):
    def level(index):
        if index >= len(nums) or nums[index] is None:
            return None
        
        root = TreeNode(nums[index])
        root.left = level(2 * index + 1)
        root.right = level(2 * index + 2)
        return root

    return level(0)

binary_tree = list_to_binarytree([3,9,20,None,None,15,7])