I have some problems when I write the recursive function.

The problem is finding the maximum total value in binary tree.

And each node can choose maximum child node.

For example, Node 8 can choose 1 and 0, then add 1.

My code is here,

triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
#result = 30
depth = 1
answer = triangle[0][0] # depth : 0
total = 0

N1,N2 = triangle[1][0], triangle[1][1]

And, I write Recursive Functions like this,

def min_max(depth, N, total):
    if depth == len(triangle):
        return total
    else:
        a,b = triangle[depth 1][triangle[depth].index(N)], triangle[depth 1][triangle[depth].index(N) 1]
        total  = max(a,b)
        N = max(a,b)
        return min_max(depth 1, N, total)

min_max(depth, N1, total)

But, I got list index out of range.

How can I fix recursive function?

CodePudding user response：

1. When you write the binary tree into python list, depth becomes index of the list. index of list always starts from 0 where as length starts from 1.(i.e list of length 5 will be having indexes ranging from 0 to 4)

So, the starting depth should be equal to 0 and the terminal condition of the recursive function should be if depth 1 == len(triangle)

Point 1 removes the index out of range issue. However we still have the problem with logic of code.

2. total = max(a,b) is checking for the maximum of the two number where as it should be looking out for maximum value of two binary tree.

Above code will parse through the single line of data with maximum values and ignores rest of the possibilities.

Below is an alternate possibility to code.

def reduce(triangle: "list[list]"):
    print(triangle, flush=True)
    print('-----------------------------------', flush=True)
    if len(triangle) == 1:
        return triangle[0][0]
    else:
        last_line = triangle.pop()
        position = 0
        for value in triangle[-1]:
            value  = max(last_line[position], last_line[position   1])
            triangle[-1][position] = value
            position  = 1
        return reduce(triangle)

print(reduce(triangle))

It works by removing the last line and adding maximum possible value to the second to last line each iteration until only one line remains

Output:

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
-----------------------------------
[[7], [3, 8], [8, 1, 0], [7, 12, 10, 10]]
-----------------------------------
[[7], [3, 8], [20, 13, 10]]
-----------------------------------
[[7], [23, 21]]
-----------------------------------
[[30]]
-----------------------------------
30