我有一些關于在二叉樹中獲得最大總和值的問題。
每個節點可以有兩個子節點（左，右）
Sum[7, 3, 8, 7, 5] 是上述示例的最大總和值。
首先，我認為選擇每個最大子節點是最好的答案，但事實并非如此。
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
depth = 0
total = []
N = triangle[0][0]
def min_max(depth, N, total):
if (depth 1) == len(triangle):
return total
else:
a,b = triangle[depth 1][triangle[depth].index(N)], triangle[depth 1][triangle[depth].index(N) 1]
total.append(max(a,b))
N = max(a,b)
return min_max(depth 1, N, total)
min_max(depth, N, total) # [8, 1, 7, 5]
然后，我想將所有案例相加并進行比較，但這似乎會使時間復雜度惡化。
這項任務的正確演算法是什么？
uj5u.com熱心網友回復：
我不完全確定問題是什么。一種簡單的遞回方式來計算節點子節點的總和就足夠了。
def get_max(node):
if not node:
return 0
return node.value max(get_max(node.left), get_max(node.right))
每個節點只被訪問一次，所以這將有一個復雜度O(number of nodes) = O(N)
uj5u.com熱心網友回復：
我猜你想要從樹根到任何孩子的路徑的最大總和。使用極小極大演算法，您可以達到大約 的時間復雜度O(2^N)，其中N是樹的深度。
但是，我在這里有一個O(N^2)針對您的問題的動態編程解決方案，N樹的深度在哪里，因此O(N^2)是樹中節點數的比例。
定義dp[i]為從樹的根到節點的路徑的最大總和i。您的基本情況是dp[root] = value of the root node. 從上到下遍歷節點（從根到子），dp函式為
dp[node] = value_of_node[node] max(dp[top_left_of[node]], dp[top_right_of[node]]);
希望這是直觀的：到某個節點的路徑的最大總和必須來自其左上角或右上角節點。
您的答案是dp樹的所有孩子值中的最大值。
uj5u.com熱心網友回復：
這個問題等于找到一條總和最大的路徑。路徑必須從根開始，以葉節點結束。
如果輸入是二叉樹的根節點，答案很容易得出。
class Node:
def __init__(self, val: int, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_sum_path(root: Node) -> int:
"""
:param root: Node
:return: the max path sum
"""
if not root:
return 0
return root.val max(max_sum_path(root.left), max_sum_path(root.right))
如果輸入是三角形（串列）。我們可以先建樹。
# create node from each element
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
triangle_nodes = []
for level_val_lst in triangle:
node_lst = [Node(e) for e in level_val_lst]
triangle_nodes.append(node_lst)
# create tree
levels = len(triangle)
for level in range(levels - 1):
node_lst = triangle_nodes[level]
next_node_lst = triangle_nodes[level 1]
cnt_nodes = len(node_lst)
for i, node in enumerate(node_lst):
left_index = i
right_index = i 1
node.left = next_node_lst[left_index]
node.right = next_node_lst[right_index]
root = triangle_nodes[0][0]
res = max_sum_path(root)
print(res)
uj5u.com熱心網友回復：
OP 帖子中的三角形是 DAG（有向無環圖），而遞回解決方案（由 Abhinav Mathur 發布）像相同高度的 BT（二叉樹）一樣遍歷它。所以遞回解為 O(N)，N 必須是 BT 中的節點數，而不是 DAG 中的節點數。如果 N 是 BT 的高度（與 DAG 相同），則復雜度變為 O(2^N)（如 Ryan Chang 所述）。
由于三角形是 DAG，我想可以將問題重新表述為在 DAG 中尋找最長路徑（三角形中的數字被認為是距離）。它在頂點和邊的數量上具有線性復雜度，O(V E)。這可能是解決這個問題的最好方法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488643.html