Python编程求解二叉树中和为某一值的路径代码示例

yipeiwu_com6年前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+Socket实现基于UDP协议的局域网广播功能示例

Python+Socket实现基于UDP协议的局域网广播功能示例

本文实例讲述了Python+Socket实现基于UDP协议的局域网广播功能。分享给大家供大家参考,具体如下: 服务器端: # udp_gb_server.py '''服务端(UDP协...

详解python 模拟豆瓣登录(豆瓣6.0)

详解python 模拟豆瓣登录(豆瓣6.0)

最近在学习python爬虫,看到网上有很多关于模拟豆瓣登录的例子,随意找了一个试了下,发现不能运行,对比了一下代码和豆瓣网站,发现原来是豆瓣网站做了修改,增加了反爬措施。 首先看下要模拟...

python中列表的切片与修改知识点总结

python中列表的切片与修改知识点总结

python中可以使用下标索引来访问列表中的值,对列表进行切片即截取,也可以对列表的数据项进行修改或更新。 使用下标索引来访问列表中的值,例如list1[1]。 使用索引截取列表中的值...

Python使用turtle库绘制小猪佩奇(实例代码)

Python使用turtle库绘制小猪佩奇(实例代码)

turtle(海龟)是Python重要的标准库之一,它能够进行基本的图形绘制。turtle图形绘制的概念诞生于1969年,成功应用于LOGO编程语言。 turtle库绘制图形有一个基本...

正确理解python中的关键字“with”与上下文管理器

前言 如果你有阅读源码的习惯,可能会看到一些优秀的代码经常出现带有 “with” 关键字的语句,它通常用在什么场景呢?今天就来说说 with 和 上下文管理器。 对于系统资源如文件、数据...