在python中查找树的最大总和 [英] Find the maximum sum of a tree in python

问题描述

我有一棵数字树，我希望能够找到数字的总和.每个数字下面是左右两个孩子所有可能的路径，我希望能够通过所有可能的路径找到最大的数字.这是一个例子

<代码> 83 1110 2 32 6

返回 8+11+32=51

我觉得这是一个递归问题，但我被我的代码困住了，并且不断出现错误.我认为我正在错误地处理这个问题.下面是我的代码:

# 返回根键值def getRootValue(root):返回根# 返回对左孩子的引用def getLeftChild(root):值=无如果 root.leftChild!=None:值=root.leftChild返回值# 返回对右孩子的引用def getRightChild(root):值=无如果 root.rightChild!=None:值 = root.rightChild返回值def sum_of_branch(根):总和=0如果 root.getLeftChild() ==None 和 root.getRightChild()==None:回程别的:回合+=回合+1keys_sum[深度]=sum+root.key返回 sum_to_deepest(root.left), sum_to_deepest(root.right)如果 root.getLeftChild()!=None:rounds+=root.getLeftChild().branchLenSum()如果 root.getRightChild()!=None:rounds+=root.getRightChild().branchLenSum()回程

解决方案

在不了解您使用的数据结构的情况下很难给您答案.但我认为您正在寻找这样的东西:

<块引用>

def sum_of_branch(root):# 如果它没有孩子，我们就到达了树的末尾.# 我们返回这个孩子的值.如果 root.getLeftChild() ==None 和 root.getRightChild()==None:返回 getRootValue(root)别的:# 如果它有孩子，我们计算每个分支的总和.leftSum = sum_of_branch(root.getLeftChild())rightSum = sum_of_branch(root.getRightChild())# 并返回它们的最大值.如果 leftSum >右和:返回 getRootValue(root) + leftSum别的:返回 getRootValue(root) + rightSum

I have a tree of numbers that I want to be able to find the sum of numbers. Below each number are two children to the left and right Of all the possible paths, I want to be able to find the biggest number through all the possible paths. Here is an example

       8
   3      11
10   2  32  6

returns 8+11+32=51

I feel that this is a recursion problem but I am stuck with my code and keep getting errors. I think that I am approaching this incorrectly. Below is my code:

# Returns root key value
def getRootValue(root):
    return root

# Returns reference to left child
def getLeftChild(root):
    value=None
    if root.leftChild!=None:
        value=root.leftChild
    return value

# Returns reference to right child
def getRightChild(root):
    value=None
    if root.rightChild!=None:
        value = root.rightChild
    return value

def sum_of_branch(root):
    sum=0  
if root.getLeftChild() ==None and root.getRightChild()==None:
    return rounds
else:
    rounds+=rounds+1
    keys_sum[depth]=sum+root.key
    return sum_to_deepest(root.left), sum_to_deepest(root.right)
    if root.getLeftChild()!=None:
        rounds+=root.getLeftChild().branchLenSum()
    if root.getRightChild()!=None:
        rounds+=root.getRightChild().branchLenSum()
    return rounds

解决方案

Without knowing the data structure you are using is difficult to give you an answer. But I think you are looking for somenthing like this:

def sum_of_branch(root):
    # If it has not childs we have arrived at the end of the tree.
    # We return the value of this child.
    if root.getLeftChild() ==None and root.getRightChild()==None:
        return getRootValue(root)
    else:
        # If it has children we calculate the sum of each branch. 
        leftSum = sum_of_branch(root.getLeftChild())
        rightSum = sum_of_branch(root.getRightChild())
        # And return the maximun of them.
        if leftSum > rightSum:
            return getRootValue(root) + leftSum
        else:
            return getRootValue(root) + rightSum

这篇关于在python中查找树的最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！