Python程序

2024-02-02 11:27| 来源: 网络整理| 查看: 265

定义二叉树结构 # Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None 构建一棵完整的二叉树 if __name__ == "__main__": # 新建节点 root = TreeNode('A') node_B = TreeNode('B') node_C = TreeNode('C') node_D = TreeNode('D') node_E = TreeNode('E') node_F = TreeNode('F') node_G = TreeNode('G') node_H = TreeNode('H') node_I = TreeNode('I') # 构建二叉树 # A # / \ # B C # / \ / \ # D E F G # / \ # H I root.left, root.right = node_B, node_C node_B.left, node_B.right = node_D, node_E node_C.left, node_C.right = node_F, node_G node_D.left, node_D.right = node_H, node_I 将列表转成二叉树

利用嵌套函数。

如下例子，将列表转化为二叉树。已知列表nums，nums = [3,9,20,None,None,15,7]，转化为下面二叉树:

在这里插入图片描述

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

在这里插入图片描述

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

递归基情况：

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

递归方程：在这里插入图片描述根据以上分析，得到如下代码，list_to_binarytree函数是嵌套函数，它里面还有一个level子函数：

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])

本文部分内容分享自微信公众号 - Python与算法社区（alg-channel）

【本文地址】

公司简介

联系我们