我在撰寫遞回函式時遇到了一些問題。
問題是在二叉樹中找到最大的總值。
每個節點可以選擇最大的子節點。
例如，節點 8 可以選擇 1 和 0，然后添加 1。
我的代碼在這里，
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]
而且，我這樣寫遞回函式，
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)
但是，我的串列索引超出了范圍。
如何修復遞回函式？
uj5u.com熱心網友回復：
- 當您將二叉樹寫入 python 串列時，深度成為串列的索引。串列的索引總是從 0 開始，而長度從 1 開始。（即長度為 5 的串列將具有從 0 到 4 的索引）
因此，起始深度應等于 0，遞回函式的終止條件應為
if depth 1 == len(triangle)
第 1 點消除了索引超出范圍的問題。但是我們仍然有代碼邏輯的問題。
total = max(a,b)正在檢查兩個數字的最大值，因為它應該尋找兩個二叉樹的最大值。上面的代碼將決議具有最大值的單行資料并忽略其余的可能性。
下面是另一種編碼的可能性。
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))
它的作業原理是洗掉最后一行并將最大可能值添加到每次迭代的倒數第二行，直到只剩下一行
輸出：
[[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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/487547.html