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

【自取】最近整理的,有需要可以领取学习:

玄魂工作室秘书 [玄魂工作室]

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

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

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

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

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

代码:

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

从树的根节点向下访问,直到叶节点经过的所有节点形成一条路径。<details><summary>*<font color='gray'>[En]</font>*</summary>*<font color='gray'>Access down from the root node of the tree until all the nodes passed by the leaf node form a path.</font>*</details>

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

"""
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()

输出:
10

5

4

3

10

5

7

10

12

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

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

Original: https://www.cnblogs.com/xuanhun/p/9547887.html
Author: 玄魂
Title: Python算法和数据结构:在二叉树中找到和为sum的所有路径

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/9912/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部