Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
48 lines (36 sloc) 1.01 KB
import os, io
import pdb
import Queue
def createRoot():
f = open('triangle.txt', 'r')
root = {}
queue = Queue.Queue()
for line in f.readlines():
line = line.split()
if not root:
root[line[0]] = {}
queue.put(root[line[0]])
continue
tmp = queue.get()
for i in range(len(line)):
if i == 0 or i == len(line)-1:
tmp[line[i]] = {}
queue.put(tmp[line[i]])
else:
child = {}
tmp[line[i]] = child
queue.put(tmp[line[i]])
tmp = queue.get()
tmp[line[i]] = child
#print line
return root
def depthFirstSearch(node, maxSum, curSum):
if not node.keys():
return curSum
for key in node.keys():
result = depthFirstSearch(node[key], maxSum, curSum+int(key))
if result > maxSum:
maxSum = result
return maxSum
root = createRoot()
print depthFirstSearch(root, 0, 0)
You can’t perform that action at this time.