python - Python max() 与 min()

Question

我有这个 python 代码，它非常适合从叶子到根节点获取最大总和。我的目标是将其更改为最小总和而不是最大总和。我以为我可以更改 min() 函数的 max() 并且它应该记录最小添加直到它到达末尾，但它对我不起作用。

我很感激任何反馈！

# This program will find the minimum cost of a binary tree

NodeMax = [0]*100
 
#Function for DepthFirstSearch traversal which stores the maximum value
#for every node until it reaches every leave
def DepthFirstSearch(values, vertex, unit, parent):
     
    #Initially NodeMax[unit] is always values[unit]
    NodeMax[unit] = values[unit - 1]
     
    #Maximum value from nodes
    maximum = 0
     
    # Traverse the tree
    for child in vertex[unit]:
         
        # continue if child is a parent 
        if child == parent:
            continue
         
        # DepthFirstSearch for further traversal
        DepthFirstSearch(values, vertex, child, unit)
         
        # keep the maximum of previous node and current node 
        maximum = max(maximum, NodeMax[child])
         
    # Add to the maximum value sent to the parent node
    NodeMax[unit] += maximum

# Function that returns the maximum value
def maximumValue(values, vertex):
    DepthFirstSearch(values, vertex, 1, 0)
    return NodeMax[1]
 
# Driver Code 
def main():     
    #amount of nodes 
    noNodes = 15
     
    # place all vertex in a list
    vertex = {}
    for i in range(noNodes + 1):
        vertex[i] = []

    values = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

    # build the tree from the diagram with undirected edges
    vertex[1].append(2), vertex[2].append(1)
    vertex[1].append(3), vertex[3].append(1)
    vertex[2].append(4), vertex[4].append(2) 
    vertex[2].append(5), vertex[5].append(2) 
    vertex[3].append(6), vertex[6].append(3)
    vertex[3].append(7), vertex[7].append(3) 
    vertex[4].append(8), vertex[8].append(4) 
    vertex[4].append(9), vertex[9].append(4) 
    vertex[5].append(10), vertex[10].append(5) 
    vertex[5].append(11), vertex[11].append(5) 
    vertex[6].append(12), vertex[12].append(6) 
    vertex[6].append(13), vertex[13].append(6)
    vertex[7].append(14), vertex[14].append(7)
    vertex[7].append(15), vertex[15].append(7)

    print("the maximum cost of this binary tree is: " + str(maximumValue(values, vertex)))

main() 

标签： pythonpython-3.x

Answer 1

maximum我猜您忘记将（现在应该是minimum）的初始值更改为inf. 我添加了if语句，因为如果它是叶子，则不应添加maximum( minimum)，因为在这种情况下它的值是inf，而不是0。

# This program will find the minimum cost of a binary tree


NodeMax = [0]*100

#Function for DepthFirstSearch traversal which stores the maximum value
#for every node until it reaches every leave
def DepthFirstSearch(values, vertex, unit, parent):
     
    #Initially NodeMax[unit] is always values[unit]
    NodeMax[unit] = values[unit - 1]
     
    #Maximum value from nodes
    maximum = float('inf')
     
    # Traverse the tree
    for child in vertex[unit]:
         
        # continue if child is a parent 
        if child == parent:
            continue
         
        # DepthFirstSearch for further traversal
        DepthFirstSearch(values, vertex, child, unit)
         
        # keep the maximum of previous node and current node 
        maximum = min(maximum, NodeMax[child])
         
    # Add to the maximum value sent to the parent node
    if len(vertex[unit]) != 1:
        NodeMax[unit] += maximum