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
投稿
猜你喜欢
- 操作系统:macOS High Sierra 10.13.3Python3.6因为此版本自带python2.7,就下载并安装了anacond
- 解决步骤:1、先打开一个cmd2、cd到你的exe文件目录3、输入 .\***.exe来源:https:
- 问题:一个文件夹c下的模块test要引用另一个包b里面模块test2的函数add,如下图解决办法:经过前辈oyljerry等的指点迷津,要在
- python中没有swich..case,若要实现一样的功能,又不想用if..elif来实现,可以充分利用字典进行实现主要是想要通过不同的k
- Javascript函数类型判断完美解决方案在判断函数类型时,我们通常使用typeof方法,一般情况下,它会得到我们所预想的效果。但是,有一
- 初级画心学Python,感觉你们的都好复杂,那我来个简单的,我是直接把心形看作是一个正方形+两个半圆:于是这就很简单了,十行代码解决:imp
- 用numpy做矩阵运算时,少不了用到矩阵乘法。本文帮你迅速区分multiply, matmul和dot的区别。numpy官方文档中的说明:(
- date() 获取日期,格式:2004-2-28 time() 获取时间,格式:22:24:59 now() 获取日期和时间 格式: 200
- 爬虫:一段自动抓取互联网信息的程序,从互联网上抓取对于我们有价值的信息,一般来说,Python爬虫程序很多时候都要使用(飞猪IP)代理的IP
- 目录1、表空间容量指标查询2、表空间扩容方式1:手工改变已存在数据文件的大小方式2:允许已存在的数据文件自动增长方式3:增加数据文件1、表空
- 本文实例分析了php中ob_flush函数和flush函数用法。分享给大家供大家参考。具体如下:ob_flush()函数: 取出PHP bu
- 在腾讯云上面搭建的mysql使用开发的电脑上navicat进行访问时总是特别的慢,原来是Mysql会对请求的地址进行域名解析,开发的电脑并没
- python有专门的神经网络库,但为了加深印象,我自己在numpy库的基础上,自己编写了一个简单的神经网络程序,是基于Rosenblatt感
- 目录什么是pyecharts?pyecharts安装加载折线图的绘制条形图和折线图的结合绘制漏斗图什么是pyecharts?pyechart
- 本文介绍了Python对于正则表达式的支持,包括正则表达式基础以及Python正则表达式标准库的完整介绍及使用示例。本文的内容不包括如何编写
- GO1.7之后,新增了context.Context这个package,实现goroutine的管理。Context基本的用法参考GOLAN
- MySQL 序列 AUTO_INCREMENT详解及实例代码MySQL序列是一组整数:1, 2, 3, ...,由于一张数据表只能有一个字段
- JAVA正则表达式及字符串的替换与分解Java 提供了 java.util.regex 包来与正则表达式进行模式匹配java.util.re
- 本文实例为大家分享了python实现图书借阅系统的具体代码,供大家参考,具体内容如下部分代码:from flask import Flask
- 本文实例为大家分享了python实现批量格式转换的具体代码,供大家参考,具体内容如下深度学习过程中总是绕不开数据集的制作,有时候实际图片格式