python3实现在二叉树中找出和为某一值的所有路径
2024-08-28 05:55:29
在二叉树中找出和为某一值的所有路径
请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径。
规则如下:
1、从最顶端的根结点,到最下面的叶子节点,计算路径通过的所有节点的和,如果与设置的某一值的相同,那么输出这条路径上的所有节点。
2、从根节点遍历树时,请请按照左到右遍历,即优先访问左子树的节点。
二叉树创建规则:从上到下一层一层的,按照从左到右的顺序进行构造
输入"10,5,12,4,7"值,构造的树如下:
1) 10
2) 10
/
5
3) 10
/\
5 12
4) 10
/\
5 12
/
4
5) 10
/\
5 12
/\
4 7
针对上面的二叉树,如果当前我们设置的“路径和”为19,那么输出结果为:
10,5,4
如果有多个路径,按到左到右的顺序遍历生成的结果每行显示一个显示。例如如果当前我们设置的“路径和”为22,那么输出结果为:
10,5,7
10,12
如果没有找到路径和为设置的值的路径,输出error。
三、输入:
输入整数N---路径和
一行字符串,多个正整数,之间用","隔开
四、输出: 满足条件的二叉树路径
五、样例输入:
22
10,5,12,4,7
六、样例输出:
10,5,7
10,12
demo:
class Node(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None class Tree(object):
lt = [] # 依次存放左右孩子未满的节点 def __init__(self):
self.root = None def add(self, number):
node = Node(number) # 将输入的数字节点化,使其具有左右孩子的属性
if self.root == None:
self.root = node
Tree.lt.append(self.root)
else:
while True:
point = Tree.lt[] # 依次对左右孩子未满的节点分配孩子
if point.left ==None:
point.left = node
Tree.lt.append(point.left) # 该节点后面作为父节点也是未满的,也要加入到列表中。
return
elif point.right ==None:
point.right = node
Tree.lt.append(point.right) # 与左孩子同理
Tree.lt.pop() # 表示该节点已拥有左右孩子,从未满列表中去除
return class Solution:
def __init__(self):
self.results = []
def RecursionFindPath(self, root, expectNumber, result):
result.append(root.val)
if root.left == None and root.right == None and sum(result) == expectNumber:
self.results.append(result)
temp = result[:]
if root.left:
self.RecursionFindPath(root.left, expectNumber, result)
result = temp[:]
if root.right:
self.RecursionFindPath(root.right, expectNumber, result)
def FindPath(self, root, expectNumber):
if root == None:
return []
self.RecursionFindPath(root, expectNumber, [])
self.results = sorted(self.results, key=len, reverse=True)
return self.results if __name__ =='__main__':
t = Tree() # 二叉树类的实例化
L = [, , , , ]
for i in L:
t.add(i) expectNum =
print(Solution().FindPath(t.root, expectNum))
输出样例:
最新文章
- Python学习之路【目录】
- Macaca-iOS入门那些事
- idea 开发环境jdk崩溃
- spring security 匿名登录
- Day12~13(2016/2/1~2/2)
- Linux环境安装jdk
- U3D刚体测试2(ForceMode,AddForce,RelativeAddForce)
- HDU 1016 Prime Ring Problem
- jQuery-弹窗登录
- 【HDOJ】2510 符号三角形
- Apache与Nginx网络模型
- 基于Verilog HDL 各种实验
- 其他信息: ORA-01400: 无法将 NULL 插入
- 读取excel 文件到datatable
- css之文本两端对齐
- linux 硬盘分区与格式化挂载 (二)
- DP常用模板
- 理解 Linux 配置文件【转】
- Linux下的常用指令汇总
- pymongo创建索引
热门文章
- 使用VSCode的Remote-SSH连接Linux进行远程开发
- [NOIP2018(PJ)] 摆渡车
- C# MVC扩展方法
- 2.(group by)如何让分组后,每组中的数据按时间倒序排列(group by和 order by的分组按排列)
- 如何更改已经pushed的commit的注释信息(How to change the pushed commit message)
- redis 解决秒杀
- Hadoop2.0之YARN组件
- 在同一个tomcat下部署多个springboot项目时,springboot项目无法正常启动的问题
- monkey工具使用(未完待续)
- CodeForces Gym 100213F Counterfeit Money