python3实现在二叉树中找出和为某一值的所有路径(推荐)
请写一个程序创建一棵二叉树，并按照一定规则，输出二叉树根节点到叶子节点的路径。
规则如下：
1、从最顶端的根结点，到最下面的叶子节点，计算路径通过的所有节点的和，如果与设置的某一值的相同，那么输出这条路径上的所有节点。
2、从根节点遍历树时，请请按照左到右遍历，即优先访问左子树的节点。
二叉树创建规则：从上到下一层一层的，按照从左到右的顺序进行构造
输入"10,5,12,4,7"值，构造的树如下：
1）10
2）10
/
5
3）10
/\
512
4）10
/\
512
/
4
5）10
/\
512
/\
47
针对上面的二叉树，如果当前我们设置的“路径和”为19，那么输出结果为:
10,5,4
如果有多个路径，按到左到右的顺序遍历生成的结果每行显示一个显示。例如如果当前我们设置的“路径和”为22，那么
输出结果为:
10,5,7
10,12
如果没有找到路径和为设置的值的路径，输出error。
三、输入:
输入整数N---路径和
一行字符串，多个正整数，之间用","隔开
四、输出:满足条件的二叉树路径
五、样例输入:
22
10,5,12,4,7
六、样例输出:
10,5,7
10,12
demo：
classNode(object): def__init__(self,x): self.val=x self.left=None self.right=None classTree(object): lt=[]#依次存放左右孩子未满的节点 def__init__(self): self.root=None defadd(self,number): node=Node(number)#将输入的数字节点化，使其具有左右孩子的属性 ifself.root==None: self.root=node Tree.lt.append(self.root) else: whileTrue: point=Tree.lt[0]#依次对左右孩子未满的节点分配孩子 ifpoint.left==None: point.left=node Tree.lt.append(point.left)#该节点后面作为父节点也是未满的，也要加入到列表中。 return elifpoint.right==None: point.right=node Tree.lt.append(point.right)#与左孩子同理 Tree.lt.pop(0)#表示该节点已拥有左右孩子，从未满列表中去除 return classSolution: def__init__(self): self.results=[] defRecursionFindPath(self,root,expectNumber,result): result.append(root.val) ifroot.left==Noneandroot.right==Noneandsum(result)==expectNumber: self.results.append(result) temp=result[:] ifroot.left: self.RecursionFindPath(root.left,expectNumber,result) result=temp[:] ifroot.right: self.RecursionFindPath(root.right,expectNumber,result) defFindPath(self,root,expectNumber): ifroot==None: return[] self.RecursionFindPath(root,expectNumber,[]) self.results=sorted(self.results,key=len,reverse=True) returnself.results if__name__=='__main__': t=Tree()#二叉树类的实例化 L=[10,5,12,4,7] foriinL: t.add(i) expectNum=22 print(Solution().FindPath(t.root,expectNum))
输出样例：
总结
以上所述是小编给大家介绍的python3实现在二叉树中找出和为某一值的所有路径，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。