Python算法之求n个节点不同二叉树个数
作者:玩蛇的 发布时间:2022-08-22 03:59:30
标签:python,二叉树
问题
创建一个二叉树
二叉树有限多个节点的集合,这个集合可能是:
空集
由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成
创建二叉树:
创建节点
再创建节点之间的关系
Python代码示例
# !/usr/bin/env python
# -*-encoding: utf-8-*-
# author:LiYanwei
# version:0.1
class TreeNode(object):
def __init__ (self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def __str__(self):
return str(self.data)
# 节点
A = TreeNode('A')
B = TreeNode('B')
C = TreeNode('C')
D = TreeNode('D')
# 节点间的关系
A.left = B
A.right = C
B.right = D
print B.right
问题
求n个节点不同二叉树个数
1个节点
根节点1 1种
1种二叉树
2个节点
根节点1 左节点1 1种(依照1节点的推断)
根节点1 右节点1 1种(依照1节点的推断)
2种二叉树
3个节点
根节点1 左节点0 右节点2 2种(依照2节点的推断)
根节点1 左节点1 右节点1 1种(依照1节点的推断)
根节点1 左节点2 右节点0 2种(依照2节点的推断)
5种二叉树
4个节点
根节点1 左节点0 右节点3 5种(依照3节点的推断)
根节点1 左节点1 右节点2 2种(依照2节点的推断)
根节点1 左节点2 右节点1 2种(依照2节点的推断)
根节点1 左节点3 右节点0 5种(依照4上面的推断)
共14种二叉树
...
n个节点
递归进行累加
Python代码示例
# !/usr/bin/env python
# -*-encoding: utf-8-*-
# author:LiYanwei
# version:0.1
# 求n个节点不同二叉树个数
def count(n):
# root : 1
# left : k
# right : n - 1- k
# s = 0
# if n == 0:
# # 空树
# return 1
s = count.cache.get(n, 0)
if s:
return s
for k in xrange(n):
s += count(k) * count(n - 1 - k)
count.cache[n] = s
return s
# 重复计算优化
count.cache = {0 : 1}
print count(100)
来源:http://www.cnblogs.com/Py00/p/7726550.html
0
投稿
猜你喜欢
- 本文实例讲述了python使用Image处理图片常用技巧。分享给大家供大家参考。具体分析如下:使用python来处理图片是非常方便的,下面提
- 字典d = {key1 : value1, key2 : value2, key3 : value3 }键必须是唯一的,但值则不必。值可以取
- 好久没有写ASP代码了,今天在做一个简单的留言本时,出现了一下错误: Microsoft Office Access Database En
- 最近在写laravel的时候遇到一个定时器的问题手动的执行 php /usr/share/nginx/html/mylaravel/arti
- 之前说过要聊聊 干职业设计经理的活 的问题,貌似有些朋友对这个事情还挺关心的,我理解为一方面是掌握对付猎头时候的标准答案,一方面是
- 在给一个 App 做 API,从服务器端的 MySQL 取出数据,然后生成 JSON。数据中有个字段叫 content,里面保存了文章内容,
- poplib模块接收邮件python的poplib模块是用来从pop3收取邮件的,也可以说它是处理邮件的第一步。POP3协议并不复杂,它也是
- 本文实例讲述了Python二叉树定义与遍历方法。分享给大家供大家参考,具体如下:二叉树基本概述:二叉树是有限个元素的几个,如果为空则为空二叉
- 很多时候,设计师们都会通过各种渠道去了解用户的需求,然而从这些渠道反馈回来的信息大部分只是用户的期望并不是真正的用户需求,但是很多时候这些期
- 用analyze进行处理,定期进行处理ANALYZE [LOCAL | NO_WRITE_TO_BINLOG] TABLE tb1_name
- 先新建一组散点充当坐标轴为了比较直观地展示旋转过程,这里通过散点来新建三个坐标轴,通过对这三个坐标轴的转动,来直观地展现转动矩阵对坐标变换的
- 生成方式Python中想要自动生成 model文件可以通过 sqlacodegen这个命令来生成对应的model文件sqlacodegen
- 一、读者指引 读者指引帮助你掌握本文的梗概。以免你看了大半才明白这编文章不适合你,给你造成视觉污染。如果你正在用ASP+XML写一些程序,或
- 最近在D4得到一本(美) Penny Mcintire写的《Visual Design for the Modern Web》.突然觉得可用
- 在印刷排版中“point”是一个绝对的单位,它等于 1/72 英寸。可以用尺子丈量的,物理的英寸。但在CSS中pt的含义
- 一.GO程序目录结构在GOPATH目录下的结构--bin(存放编译后生成的可执行文)|----hello.exe(可执行文件)--pkg(存
- 简介在SQL SERVER中,数据库在硬盘上的存储方式和普通文件在Windows中的存储方式没有什么不同,仅仅是几个文件而已.SQL SER
- 用于匹配的正则表达式为 :([1-9]\d*\.?\d*)|(0\.\d*[1-9])([1-9] :匹配1~9的数字;\d :匹配数字,包
- 前言Github源码地址本文同时也是学习唐宇迪老师深度学习课程的一些理解与记录。文中代码是实现在TensorFlow下使用卷积神经网络(CN
- 先来看个例子:#-*- coding:utf8 -*-s = u'中文截取's.decode('utf8')