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

yipeiwu_com5年前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中列表的切片与修改知识点总结

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

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

Python __getattr__与__setattr__使用方法

比如下面的例子: class Book(object):    def __setattr__(self, name, value):  ...

Python版微信红包分配算法

红包分配算法代码实现发给大家,祝红包大丰收! #coding=gbk import random import sys #print random.randint(0, 99)...

pycharm debug功能实现跳到循环末尾的方法

pycharm debug功能实现跳到循环末尾的方法

可以使用条件断点,如图,在断点上右键可以设置,条件自己输入,python语法: 以上这篇pycharm debug功能实现跳到循环末尾的方法就是小编分享给大家的全部内容了,希望能给大家...

python 一篇文章搞懂装饰器所有用法(建议收藏)

python 一篇文章搞懂装饰器所有用法(建议收藏)

01. 装饰器语法糖 如果你接触 Python 有一段时间了的话,想必你对 @ 符号一定不陌生了,没错 @ 符号就是装饰器的语法糖。 它放在一个函数开始定义的地方,它就像一顶帽子一样戴...