Python算法和数据结构:在二叉树中找到和为sum的所有路径

思路:先用递归创建一颗二叉树,作为输入;然后对这课二查树进行递归遍历,递归中每遍历一个节点,下次递归的和为sum-data;并用一个数组记录遍历过的路径,当存在sum时,输出数组中的路径。

下图为树的输入,输入的数组为:

[10,5,4,None,3,None,None,7,None,None,12,None,None]

没有子节点的用None表示,构造树时用递归先构造左子树。

代码:

"""
题目:输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

"""
class TreeNode:
    """
    树的节点定义,后面的很多操作都是基于节点的
    """

    def __init__(self): 
        """
        定义一个树的节点,初始状态左右节点为空
        """
        self.leftNode = None
        self.rightNode = None

    def setData(self, data):
        """
        设置数字的方法
        args: data节点值
        """
        self.data = data

    def setLeftNode(self, leftNode):
        """
        设置左节点的方法
        args: leftNode 左节点
        """
        self.leftNode = leftNode

    def setRightNode(self, rightNode):
        """
        设置右节点的方法
        args: rightNode 右节点
        """
        self.rightNode = rightNode

    def getData(self):
        """
        获取节点数字
        return:返回节点数字
        """
        return self.data

    def getLeftNode(self):
        """
        获取左节点
        return:返回左节点
        """
        return self.leftNode

    def getRightNode(self):
        """
        获取右节点
        return:返回右节点
        """
        return self.rightNode


class test:
    def __init__(self):
        """
        test类的初始化,用来构造树和调用查找算法
        return:返回右节点
        """ 
        #self.tree = self.build_tree()
        self.index = 0
        self.data = [10,5,4,None,3,None,None,7,None,None,12,None,None]
        self.tree = self.build_node()
        tempNode = self.tree
        data_list = []
        self.findSum(tempNode, 22, data_list)

    def build_node(self):
        """
        根据输入,用递归的方法,构造树的方法

        """ 
        if self.index < len(self.data):
            curr_data = self.data[self.index]
            self.index = self.index + 1
            if curr_data != None:
                onNode = TreeNode()     
                onNode.setData(curr_data)       
                left_node = self.build_node()
                onNode.setLeftNode(left_node)
                right_node = self.build_node()

                onNode.setRightNode(right_node)
                return onNode



    def findSum(self,node, needsum, data_list):
        """
        递归调用findSum,查找和是needsum的路径
        args:node是树的根节点,每次递归的是节点移动
            needsum是需要求的和
            data_list里面存的是路径

        """ 
        if node != None and node.getData() <= needsum :
            if node.getData() < needsum:
                #print node.getData()
                newSum = needsum - node.getData()
                curr_data = node.getData()
                data_list.append(curr_data)
                self.findSum(node.getLeftNode(), newSum, data_list)
                self.findSum(node.getRightNode(), newSum, data_list)
                data_list.pop()

            else:
                #开始打印输出路径
                if node.getData() == needsum:
                    for d in data_list:
                        print d
                    print node.getData()
                    print '-----------'


if __name__ == "__main__":   
    onNode = test()输出:10543-----------1057-----------1012-----------

欢迎关注订阅号:白话算法

原文发布于微信公众号 - 玄魂工作室(xuanhun521)

原文发表时间:2018-08-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

南阳理工大学oj 题目15 括号匹配(二)

括号匹配(二) 时间限制:1000 ms  |  内存限制:65535 KB 难度:6 描述给你一个字符串,里面只包含"(",")","[","]"四种符号,请...

35512
来自专栏王磊的博客

javascript数组去重方法汇总

前言 ---- 数组去重已经是一个老生常谈的问题了,依然经久不息,经过岁月的变迁es标准的升级迭代,似乎有越来越多的方法和方式供我们使用,那么那种方式才是最...

2839
来自专栏王磊的博客

javascript数组去重方法汇总

1253
来自专栏生信小驿站

Python数据处理从零开始----第三章(pandas)①删除列目录

在这里默认:axis=0,指删除index,因此删除columns时要指定axis=1; inplace=False,默认该删除操作不改变原数据,而是返回一个...

702
来自专栏Phoenix的Android之旅

两个数值相等的Integer不一定相等,为什么

昨天说到两个值是128的 Integer 对象 用 == 来比较的话结果是 false, 今天解释下为什么

1093
来自专栏云霄雨霁

Java--类和对象之组合和继承

2347
来自专栏java学习

Java每日一练(2017/7/26)

本期题目: (单选题)1、一个文件中的字符要写到另一个文件中,首先需要()。 A 使用标准输出流System.out.println()。 B 建立文件字符输...

3026
来自专栏mathor

LeetCode90. 子集 II

 升级版子集问题,最简单的办法,先把所有元素存储到set中去重,然后再重新赋值给数组,再dfs,但这样做太简单了,没什么难度,于是换了一种做法,不去重,直...

2112
来自专栏Hongten

java中的Integer的toBinaryString()方法

在一次面试的过程中,遇到过这样的题目,题目的大概意思是:让写出Integer类中的toBinaryString()方法

1002
来自专栏

Python 学习笔记:需要仔细阅读一个函数

994

扫码关注云+社区

领取腾讯云代金券