Python编程求解二叉树中和为某一值的路径代码示例
题目描述
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路:首先要理解题意,是从根节点往子节点连。
1、如果只有根节点或者找到叶子节点,我们就把其对应的val值返回
2、如果不是叶子节点,我们分别对根节点的左子树、右子树进行递归,直到找到叶子结点。然后遍历把叶子结点和父节点对应的val组成的序列返回上一层;如果没找到路径,其实也返回了序列,只不过是[]
代码如下:
# -*- coding:utf-8 -*- class TreeNode(): def __init__(self,x): self.val = x self.left = None self.right = None def function(root,target_number): result = [] if not root: return result # 如果只有根节点或者找到叶子节点,我们就把其值返回 if not root.left and not root.right and root.val == target_number: return [[root.val]] else: # 如果不是叶子节点,我们分别对根节点的左子树、右子树进行递归,注意修改变量: left = function(root.left,target_number - root.val) right = function(root.right,target_number - root.val) for item in left+right: result.append([root.val]+item) return result
总结
以上就是本文关于Python编程求解二叉树中和为某一值的路径代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
Python探索之创建二叉树
Python算法之求n个节点不同二叉树个数
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
相关推荐
-
python先序遍历二叉树问题
问题 如何遍历一个二叉树 遍历二叉树就是访问二叉树的每一个节点 二叉树父结点下先左访问,先序遍历(根左右) 例如:遍历以下的二叉树 遍历结果:ABDECF Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): ''' 二叉树类 ''' def __init__ (self, data, left = None, right
-
python实现二叉树的遍历
本文实例为大家分享了python实现二叉树的遍历具体代码,供大家参考,具体内容如下 代码: # -*- coding: gb2312 -*- class Queue(object): def __init__(self): self.q = [] def enqueue(self, item): self.q.append(item) def dequeue(self): # if self.q != []: if len(self.q)>0: return self.q.pop(0) else
-
Python编程实现双链表,栈,队列及二叉树的方法示例
本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法.分享给大家供大家参考,具体如下: 1.双链表 class Node(object): def __init__(self, value=None): self._prev = None self.data = value self._next = None def __str__(self): return "Node(%s)"%self.data class DoubleLinkedList(object): def
-
Python数据结构与算法之二叉树结构定义与遍历方法详解
本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历 采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde
-
Python编程把二叉树打印成多行代码
题目描述 从上到下按层打印二叉树,同一层结点从左至右输出.每一层输出一行. 思路: 1.把每层节点的val值用list存好 2.把每层节点存好: ①计算当层节点的个数,这样就保证下一步每层的结点都被pop光 ②然后依次弹出从左到右的每个节点,然后在list中加入该节点对应的左结点.右节点(如果存在的话) 代码如下: class TreeNode(): def __init__(self,x): self.val = x self.left = None self.right = None def
-
Python二叉树的定义及常用遍历算法分析
本文实例讲述了Python二叉树的定义及常用遍历算法.分享给大家供大家参考,具体如下: 说起二叉树的遍历,大学里讲的是递归算法,大多数人首先想到也是递归算法.但作为一个有理想有追求的程序员.也应该学学非递归算法实现二叉树遍历.二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开. 以下直入主题: 定义一颗二叉树,请看官自行想象其形状, class BinNode( ): def __init__( self, val ): self.lchild = None self.rchild =
-
Python算法之求n个节点不同二叉树个数
问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树: 创建节点 再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, righ
-
Python实现基于二叉树存储结构的堆排序算法示例
本文实例讲述了Python实现基于二叉树存储结构的堆排序算法.分享给大家供大家参考,具体如下: 既然用Python实现了二叉树,当然要写点东西练练手. 网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解. 但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序 其中最难的问题就是交换二叉树中两个节点. 因为一个节点最多与三个节点相连,那么两个节点互换,就需要考虑到5个节点之间的关系,也需要判断是左右孩子,这将是
-
Python编程求解二叉树中和为某一值的路径代码示例
题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 思路:首先要理解题意,是从根节点往子节点连. 1.如果只有根节点或者找到叶子节点,我们就把其对应的val值返回 2.如果不是叶子节点,我们分别对根节点的左子树.右子树进行递归,直到找到叶子结点.然后遍历把叶子结点和父节点对应的val组成的序列返回上一层:如果没找到路径,其实也返回了序列,只不过是[] 代码如下: # -*- coding:utf-
-
php实现二叉树中和为某一值的路径方法
二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.(注意: 在返回值的list中,数组长度大的数组靠前) 思路: 1.二叉树的前序遍历,中左右顺序 2.把目标值target传进去,target-=val 3.target为0并且left和right都为null,达到叶结点 4.函数外部两个数组,list数组存一条路径,listAll数组存所有路径 FindPath(roo
-
Python编程tkinter库Canvas实现涂鸦颜色表及围棋盘示例
目录 tkinter库Canvas操作三个实例 实例一:涂鸦 运行效果图: 其它作图函数: 实例二:颜色表 运行效果图: 实例三:围棋盘 运行效果图: tkinter库Canvas操作三个实例 实例一:涂鸦 import tkinter as tk import pyautogui as ag from time import sleep def paint(event): x1, y1 = (event.x - 1), (event.y - 1) x2, y2 = (event.x + 1),
-
Java编程通过list接口实现数据的增删改查代码示例
List接口常用的实现ArrayList. 常用方法:add(Object obj) 增加一个元素 add(int index,Object obj) 在指定索引位置添加元素 remove(int index) 删除指定位置的元素 remove(Objiect) 从列表中删除元素 set(index,Object) 修改指定位
-
Python编程实现两个文件夹里文件的对比功能示例【包含内容的对比】
本文实例讲述了Python编程实现两个文件夹里文件的对比功能.分享给大家供大家参考,具体如下: #-*-coding:utf-8-*- #=============================================================================== # 目录对比工具(包含子目录 ),并列出 # 1.A比B多了哪些文件 # 2.B比A多了哪些文件 # 3.二者相同的文件:文件大小相同 VS 文件大小不同 (Size相同文件不打印:与Size不同文件显
-
Python编程实现下载器自动爬取采集B站弹幕示例
目录 实现效果 UI界面 数据采集 小结 大家好,我是小张! 在<Python编程实现小姐姐跳舞并生成词云视频示例>文章中简单介绍了B站弹幕的爬取方法,只需找到视频中的参数 cid,就能采集到该视频下的所有弹幕:思路虽然很简单,但个人感觉还是比较麻烦,例如之后的某一天,我想采集B站上的某个视频弹幕,还需要从头开始:找cid参数.写代码,重复单调: 因此我在想有没有可能一步到位,以后采集某个视频弹幕时只需一步操作,比如输入想爬取的视频链接,程序能自动识别下载 实现效果 基于此,借助 PyQt5
-
Python编程根据字典列表相同键的值进行合并
目录 一.前言 两个列表的数据为: 期望合并的结果 二.实现分析 三.总结 一.前言 今天有粉丝咨询了一个问题,他现在有两个列表,它们的元素都为字典,且字典都有一个key为id,现在想把这两个字典根据id合并为一个字典,类型下面的效果: 两个列表的数据为: a_list = [{'id': 1, 'value': 11}, {'id': 2, 'value': 22}, {'id': 3, 'value': 33}] b_list = [{'id': 1, 'name': 'a'}, {'id'
-
Python编程实现二叉树及七种遍历方法详解
本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl
-
C++实现查找二叉树中和为某一值的所有路径的示例
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径. 打印出和与输入整数相等的所有路径. 例如 输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7. 先序遍历树即可得到结果. 算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算,sum为栈中的元素的和,target为目标值. 到达一个节点之后计算当前节点和sum的和,如果为target,输出路径返回,如果大于target,则直接返回,如果小
随机推荐
- AngularJS过滤器filter用法分析
- MongoDB的安装及配置文件选项全解
- jQuery+CSS实现滑动的标签分栏切换效果
- js右下角与漂浮广告代码(兼容多浏览器)
- WinForm自定义函数FindControl实现按名称查找控件
- ASP.NET 中ImageMap控件的用法
- 浅谈在Swift中关于函数指针的实现
- Display SQL Server Version Information
- golang语言中for循环语句用法实例
- C/C++ 编译器优化介绍
- Android实现标题显示隐藏功能
- Ajax()方法如何与后台交互
- jquery实现div阴影效果示例代码
- Android studio 下的APK打包失败问题解决办法
- Python使用爬虫猜密码
- jQuery下拉菜单的实现代码
- 窗体滚动条出现在左侧的实例代码
- Android实现仿通讯录侧边栏滑动SiderBar效果代码
- Android下如何使用百度地图sdk
- Postgresql查询效率计算初探