python3实现在二叉树中找出和为某一值的所有路径(推荐)

yipeiwu_com6年前Python基础

请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径。

规则如下:

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[0] # 依次对左右孩子未满的节点分配孩子
       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(0) # 表示该节点已拥有左右孩子,从未满列表中去除
         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 = [10, 5, 12, 4, 7]
 for i in L:
   t.add(i)
 expectNum = 22
 print(Solution().FindPath(t.root, expectNum))

输出样例:

总结

以上所述是小编给大家介绍的python3实现在二叉树中找出和为某一值的所有路径,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对【听图阁-专注于Python设计】网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

相关文章

Python实现简易端口扫描器代码实例

Python实现简易端口扫描器代码实例

在网上的一些资料的基础上自己又添了些新内容,算是Python socket编程练手吧。 #coding=utf-8 import socket import time import...

深入浅析Python中join 和 split详解(推荐)

python join 和 split方法简单的说是:join用来连接字符串,split恰好相反,拆分字符串的。 .join()   join将 容器对象 拆分并以指定的字符将列表内的元...

pymysql 开启调试模式的实现

pymysql 开启调试模式的实现

今天在排查线上一个奇怪的数据库连接问题,所以打开了 pymysql 的源码在阅读,发现 pymysql 在其 connections 模块里内置了一个 DEBUG 变量用于控制是否开启调...

Python Requests模拟登录实现图书馆座位自动预约

本文实例为大家分享了Python实现图书馆座位自动预约的具体代码,供大家参考,具体内容如下 配置 通过公网主机定时运行脚本,并发送邮件到自己的qq邮箱,这样在微信就会有消息提示是否预约成...

用python 实现在不确定行数情况下多行输入方法

如下所示: stopword = '' str = '' for line in iter(raw_input, stopword): str += line + '\n' pri...