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

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

规则如下：

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实现在二叉树中找出和为某一值的所有路径，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

赞 (0)

相关推荐

  • python二叉树的实现实例

    树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱.树的递归定义如下:(1

  • Python探索之创建二叉树

    问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树,创建节点,再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, right

  • python数据结构之二叉树的遍历实例

    遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:   1).访问结点本身(N)   2).遍历该结点的左子树(L)   3).遍历该结点的右子树(R) 有次序:   NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历))  --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)

  • python实现的二叉树定义与遍历算法实例

    python实现的二叉树定义与遍历算法实例

    本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l

  • Python中的二叉树查找算法模块使用指南

    python中的二叉树模块内容: BinaryTree:非平衡二叉树  AVLTree:平衡的AVL树  RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree  FastAVLTree  FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py

  • Python简单定义与使用二叉树示例

    本文实例讲述了Python简单定义与使用二叉树的方法.分享给大家供大家参考,具体如下: class BinaryTree: def __init__(self,rootObj): self.root = rootObj self.leftChild = None self.rightChild = None def insertLeft(self,newNode): if self.leftChild == None: self.leftChild = BinaryTree(newNode) e

  • Python实现重建二叉树的三种方法详解

    Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • Python利用前序和中序遍历结果重建二叉树的方法

    Python利用前序和中序遍历结果重建二叉树的方法

    本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''

  • Python编程实现二叉树及七种遍历方法详解

    Python编程实现二叉树及七种遍历方法详解

    本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl

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

    请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径. 规则如下: 1.从最顶端的根结点,到最下面的叶子节点,计算路径通过的所有节点的和,如果与设置的某一值的相同,那么输出这条路径上的所有节点. 2.从根节点遍历树时,请请按照左到右遍历,即优先访问左子树的节点. 二叉树创建规则:从上到下一层一层的,按照从左到右的顺序进行构造 输入"10,5,12,4,7"值,构造的树如下: 1) 10 2) 10       /     5 3) 10        /\   

  • 如何在二叉树中找出和为某一值的所有路径

    代码如下所示,不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,在二叉树中找出和为某一值的所有路径#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;static int sum(0);static int count(0);templat

  • python中找出numpy array数组的最值及其索引方法

    在list列表中,max(list)可以得到list的最大值,list.index(max(list))可以得到最大值对应的索引 但在numpy中的array没有index方法,取而代之的是where,其又是list没有的 首先我们可以得到array在全局和每行每列的最大值(最小值同理) >>> a = np.arange(9).reshape((3,3)) >>> a array([[0, 1, 2], [9, 4, 5], [6, 7, 8]]) >>&

  • python实现从一组颜色中找出与给定颜色最接近颜色的方法

    本文实例讲述了python实现从一组颜色中找出与给定颜色最接近颜色的方法.分享给大家供大家参考.具体分析如下: 这段代码非常有用,可以找到指定颜色相似的颜色,比如有一组8个颜色,现在给定一个rgb格式的演示,找出它与8个颜色中的哪一个最接近,如果你需要做一个按照图片颜色搜索图片的程序,这个就非常有用了. 复制代码 代码如下: from colorsys import rgb_to_hsv colors = dict(( ((196, 2, 51), "RED"), ((255, 165

  • Java实现从字符串中找出数字字符串的方法小结

    本文实例总结了Java实现从字符串中找出数字字符串的方法.分享给大家供大家参考,具体如下: int start = 0; String numStr = null; for (int j = 0; j < valuesStr.length() - 1; j++) { if (Character.isDigit(valuesStr.charAt(j)) == false && Character.isDigit(valuesStr.charAt(j + 1)) == true) { s

  • 字符串中找出连续最长的数字字符串的实例代码

    复制代码 代码如下: //1. 写一个函数,它的原形是int continumax(char *outputstr,char *intputstr) //功能: //在字符串中找出连续最长的数字串,并把这个串的长度返回, //并把这个最长数字串付给其中一个函数参数outputstr所指内存. //例如:"abcd12345ed125ss123456789"的首地址传给intputstr后,函数将返回9,outputstr所指的值为123456789 #include<stdio.

  • 在Framework 4.0中:找出新增的方法与新增的类(二)

    在Framework 4.0中:找出新增的方法与新增的类(二)

    问题描述:在Framework 4.0中:找出新增的方法与新增的类(一) 为什么动态加载程序集无法找出Framework 4.0 和Framwork2.0 新增的方法和类? 因为控制台程序默认就添加了Framework4.0的程序集,当你使用Object,Type,string这些类的时候就已经在使用已经加载的程序集了,而clr不会重复的去加载程序集??,这点记不清了.所以V2Assembly 和v4Assembly都是Framework4.0的Assembly. 验证: 复制代码 代码如下:

  • Python 实现Numpy中找出array中最大值所对应的行和列

    Python特别灵活,肯定方法不止一种,这里介绍一种我觉得比较简单的方法. 如下图,使用x == np.max(x) 获得一个掩模矩阵,然后使用where方法即可返回最大值对应的行和列. where返回一个长度为2的元组,第一个元素保存的是行号,第二个元素保存的是列号. 以上这篇Python 实现Numpy中找出array中最大值所对应的行和列就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • python 已知一个字符,在一个list中找出近似值或相似值实现模糊匹配

    已知一个元素,在一个list中找出相似的元素 使用场景: 已知一个其它来源的字符串, 它有可能是不完全与我数据库中相应的字符串匹配的,因此,我需要将其转为适合我数据库中的字符串 使用场景太绕了, 直接举例来说吧 随便举例: 按青岛城市的城区来说, 我数据库中存储的城区是个list:['市北区', '市南区', '莱州市', '四方区']等 从其它的数据来源得到一个城区是:市北 我怎么得到与市北相似相近的市北区 解决方案: In [1]: import difflib In [2]: cityar

  • 详解PHP如何在两个大文件中找出相同记录

    详解PHP如何在两个大文件中找出相同记录

    目录 1.引言 2.思路 3.实操 4.生成测试文件 5.分割文件 6.查找重复记录 7.完整代码 1.引言 给定a,b两个文件, 分别有x,y行数据, 其中(x, y均大于10亿), 机器内存限制100M,该如何找出其中相同的记录? 2.思路 处理该问题的困难主要是无法将这海量数据一次性读进内存中. 一次性读不进内存中,那么是否可以考虑多次呢?如果可以,那么多次读入要怎么计算相同的值呢? 我们可以用分治思想, 大而化小.相同字符串的值hash过后是相等的, 那么我们可以考虑使用hash取模,

随机推荐