DFS Flashcards
sorted array to binary tree
def convert(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = convert(left, mid - 1)
node.right = convert(mid + 1, right)
return node
return convert(0, len(nums) - 1)Root to leaf paths
preorder and inbetween recursive calls check condition if its leaf node print stack
end of recursive calls stack.pop()
stack=[]
def preorder(root,stack):
if root==None:
return None
stack.append(root.val)
preorder(root.left,stack)
if root.left==None and root.right==None:
print(stack)
preorder(root.right,stack)
stack.pop()
Path sum
if root==None:
return False
sum1-=root.val
if root.left==None and root.right==None:
return sum1==0
return self.hasPathSum(root.left,sum1) or self.hasPathSum(root.right,sum1)
Min Depth
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root==None:
return 0
if root.left==None and root.right==None:
return 1
mindepth=float('inf')
if root.left:
mindepth=min(mindepth,self.minDepth(root.left))
if root.right:
mindepth=min(mindepth,self.minDepth(root.right))
return mindepth+1
Longets Increasing path in matrix
we find decreasing so the result will be same.
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if len(matrix)==0:
return 0
m=len(matrix)
n=len(matrix[0])
dp=[[0]*n for i in range(m)]
def dfs(i,j):
if not dp[i][j]:
val=matrix[i][j]
dp[i][j]=1+max(dfs(i-1,j) if i and val> matrix[i-1][j] else 0,
dfs(i+1,j) if i matrix[i+1][j] else 0,
dfs(i,j-1) if j and val> matrix[i][j-1] else 0,
dfs(i,j+1) if jmatrix[i][j+1] else 0)
return dp[i][j]
return max(dfs(x,y) for x in range(m) for y in range(n))
find root to sum path
here we will define self function and append value to resultant when leaf node occurs
class Solution(object):
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res=0
self.dfs(root,0)
return self.res
def dfs(self,root,value):
if root:
value= value*10+root.val
self. dfs(root.left,value)
self. dfs(root.right,value)
if root.left==None and root.right==None:
self.res+=value
path sum II
simple dfs only two conditions extra if you want to track all nodes from root to leaf store into stack sum of values
if root==None:
return []
stack=[]
stack.append(([root.val],root))
res=[]
while stack:
value,node=stack.pop()
if node.left==None and node.right==None and sum(value)==sum1:
res.append(value)
if node.left:
stack.append((value+[node.left.val],node.left))
if node.right:
stack.append((value+[node.right.val],node.right))
return res
Course Schedule II
4, [[1,0],[2,0],[3,1],[3,2]]
toplogical sort
dict1 holds prere-courses
nei just adjacency list
we make sure here pop independent subject that any subject on dependent on it for prereq but thi smay be depend on other for prereq
append to list
make sure it remove connections with all its neighbors
in dict
if dict1 node is left empty without this then add that node to stack
remve this node from dict1.
class Solution(object):
def findOrder(self, numCourses, prerequisites):
“””
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
“””
dict1=collections.defaultdict(set)
neigh=collections.defaultdict(set)
res=[]
for i,j in prerequisites:
dict1[j].add(i)
neigh[i].add(j)
stack = [i for i in range(numCourses) if not dict1[i]]
while stack:
node=stack.pop()
for i in neigh[node]:
dict1[i].remove(node)
if not dict1[i]:
stack.append(i)
dict1.pop(node)
res.append(node)
return res[::-1] if not dict1 else []
Binary Tree Maximum Path Sum
loop throght subtress and get the max value.
class Solution:
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root==None:
return 0
self. res=float('-inf')
self. dfs(root)
return self.res
def dfs(self,root):
if not root:
return 0
if root:
left=self.dfs(root.left)
right=self.dfs(root.right)
totalpath=root.val+left+right
sum1=root.val+max(left,right,0)
self.res=max(self.res,totalpath,sum1)
return sum1
- Max Area of Island
class Solution:
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
self. m=len(grid)
self. n=len(grid[0])
self.res=0
for i in range(self.m):
for j in range(self.n):
if grid[i][j]==1:
self.res=max(self.res,self.dfs(i,j,grid))
return self.res
def dfs(self,i,j,grid):
grid[i][j]='#'
return 1+(self.dfs(i-1,j,grid) if i and grid[i-1][j]==1 else 0)+(self.dfs(i+1,j,grid) if i
Word ladder 2
def findLadders(self, start, end, dictV):
wordlist=set(dictV)
layer={}
res=[]
layer[start]=[[start]]
while layer:
newlayer=defaultdict(list)
for w in layer:
if w==end:
res.extend(k for k in layer[w])
else:
for i in range(len(w)):
for j in string.ascii_lowercase:
newword=w[:i]+j+w[i+1:]
if newword in wordlist:
newlayer[newword]+=[j+[newword] for j in layer[w]]
wordlist -= set(newlayer.keys())
layer = newlayer
return res
