ziqiyang88
BAN USERimport collections
class TreeNode(object):
def __init__(self,x,y):
self.x = x
self.y = y
self.left = None
self.right = None
class Solution(object):
def sameLevel(self,root,x,y):
if not root:
return False
queue = collections.deque([(root,0)])
level = 0
sameLevel = [False,False]
while queue:
node = queue.popleft()
node[1]!=level:
level+=1
sameLevel = [False,False]
if node[0].left:
queue.append((node[0].left,level+1))
if node[0].right:
queue.append((node[0].right,level+1))
if node[0].x == x:
sameLevel[0] = True
if node[0].y == y:
sameLevel[1] = True
if sameLevel == [True,True]:
return True
return False
class Solution(object):
def maxPath(self,grid):
if not grid or not grid[0]:
return 0
res = 0
for i in xrange(len(grid)):
if grid[i][0] != -1:
sumRes = []
self.dfs(grid,i,0,0,sumRes)
res = max(res,max(sumRes))
return res
def dfs(self,grid,i,j,path,sumRes):
if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
return
if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
sumRes.append(path+grid[i][j])
return
temp = grid[i][j]
grid[i][j] = -1
self.dfs(grid,i-1,j,path+temp,sumRes)
self.dfs(grid,i+1,j,path+temp,sumRes)
self.dfs(grid,i,j+1,path+temp,sumRes)
grid[i][j] = temp
return sumRes
- ziqiyang88 March 12, 2016