B
Man kann das als Graphenproblem betrachten (der Graph ist sogar azyklisch). Jede Zahl ist ein Knoten, es gibt von jedem Knoten, der kein Blatt ist, zwei Kanten zu seinen beiden Nachfolgern. Es geht jetzt darum, zu jedem Blatt den Pfad zu finden, bei dem die Summe der Zahlen am größten ist. Dazu speichert man in jedem Knoten zwei Dinge:
die maximal erreichbare Summe bis dorthin
von welchem Vorgängerknoten man dorthin gekommen ist (diese Information entfällt beim Startknoten a)
Jetzt geht man den Baum ebenenweise durch:
maximal erreichbare Summe bei a ist a
bei b: a+b, bei c: a+c (soweit noch uninteressant)
bei d: a+b+d
bei e: a+b+e oder a+c+e, je nachdem welches größer ist. Entsprechend wird in e vermerkt, ob der Vorgänger b oder c ist, so dass man später den Pfad zurückverfolgen kann.
bei f: a+c+f.
usw., die maximal erreichbare Summe bei einem Knoten x ist immer das Maximum der erreichbaren Summen der beiden Vorgänger von x plus x.
Es ist wichtig zu erkennen, dass, egal was weiter unten noch passiert, sich die maximal erreichbare Summe weiter oben nicht mehr ändern kann. Man kann also unbesorgt Ebene für Ebene abarbeiten und hat irgendwann die maximal erreichbare Summe für jedes Blatt, sowie über die Rückwärtskanten den Pfad, der auf diese Summe führt.
Das ist übrigens eine einfache Variante von Dijkstras Algorithmus zur Bestimmung kürzester Pfade in Graphen.