Skip to content

Instantly share code, notes, and snippets.

@taixingbi

taixingbi/*bfs.java

Last active June 10, 2019 22:59
Show Gist options
  • Save taixingbi/0b516408de328450d480788ceab35a90 to your computer and use it in GitHub Desktop.
Save taixingbi/0b516408de328450d480788ceab35a90 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
*bfs.java
Level Order Traversal: 102 / 107 / 637
/582
102. Binary Tree Level Order Traversal
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
class Solution {
public List<List<Integer>> breathFirstTree(TreeNode root) {
List<List<Integer>> levels= new ArrayList<>();
if(root==null) return levels;
Queue<TreeNode> nodes= new LinkedList<>();
nodes.add(root);
while(!nodes.isEmpty()) {
int N= nodes.size();
List<Integer> level= new ArrayList<>();
for(int i=0; i<N; ++i) {
TreeNode node= nodes.remove();
level.add(node.val);
if(node.left!=null) nodes.add(node.left);
if(node.right!=null) nodes.add(node.right);
}
levels.add(level);
//levels.add(0, level);
}
System.out.println("\nbfs: "+levels);
return levels;
}
}
429. N-ary Tree Level Order Traversal
https://leetcode.com/problems/n-ary-tree-level-order-traversal/description/
class Solution(object):
def levelOrder(self, root):
"""
:type root: Node
:rtype: List[List[int]]
"""
#-----------------------------------bfs-----------------------------------------
if not root: return []
nodes= [root]
ans= []
while nodes:
nextNodes= []
level= []
for node in nodes:
level.append(node.val)
for child in node.children: nextNodes.append(child)
ans.append(level)
nodes= nextNodes
return ans
107. Binary Tree Level Order Traversal II
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# runtime complexity: O(n) n= number of nodes space complexity: O(m) n + m m= maximun depth of tree to save call stack
#--------------------bfs----------------------
if not root: return []
ans= []
nodes= [root]
while nodes:
nextNodes=[]
level=[]
for node in nodes:
level.append(node.val)
if node.left: nextNodes.append(node.left)
if node.right: nextNodes.append(node.right)
ans = [level] + ans
nodes= nextNodes
return ans
199. Binary Tree Right Side View
https://leetcode.com/problems/binary-tree-right-side-view/
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans= []
if not root: return ans
nodes= [root]
while nodes:
nextNodes= []
ans.append(nodes[-1].val)# right view node
for node in nodes:
if node.left: nextNodes.append(node.left)
if node.right: nextNodes.append(node.right)
nodes= nextNodes
return ans
637. Average of Levels in Binary Tree
https://leetcode.com/problems/average-of-levels-in-binary-tree/description/
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
# runtime complexity: O(n) n= number of nodes space complexity: O(m) n + m m= maximun depth of tree to save call stack
#---------------------bfs-------------------------------------------------
if not root: return 0;
ans= []
nodes= [root] # queue
while(nodes):
Sum= 0
Nextnodes= []
for node in nodes:
Sum+= node.val
if(node.left): Nextnodes.append(node.left)
if(node.right): Nextnodes.append(node.right)
ans.append(1.0*Sum/len(nodes))
nodes= Nextnodes
return ans
582. Kill Process
https://leetcode.com/problems/kill-process/description/
Input:
pid = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
3
/ \
1 5
/
10
Kill 5 will also kill 10.
class Solution(object):
def killProcess(self, pid, ppid, kill):
"""
:type pid: List[int]
:type ppid: List[int]
:type kill: int
:rtype: List[int]
"""
#----------------bfs--------------------------
#runtime complexity: O(n) n= all nodes spacce complexity: O(n)
d= collections.defaultdict(list)
for i, pp in enumerate(ppid):
d[pp].append(pid[i]) #parent -> child
q= [kill]
ans= []
while q:
qnext= []
for pp in q:
ans.append(pp)
if pp in d:
qnext.extend(d[pp])
q= qnext
return ans
117. Populating Next Right Pointers in Each Node II
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
#-------------------bfs----------------
if not root: return
nodes = [root]
while nodes:
level = []
for node in nodes:
if node.left: level.append(node.left)
if node.right: level.append(node.right)
for i in range(len(nodes)-1): nodes[i].next = nodes[i+1]
nodes = level
Raw
BfsCol.java
314. Binary Tree Vertical Order Traversal
https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/
Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
/\
/ \
5 2
Output:
[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
public List<List<Integer>> advance(TreeNode root) {
List<List<Integer>> levels= new ArrayList<List<Integer>>();
if(root==null) return levels;
Queue<TreeNode> nodes= new LinkedList<>();
Queue<Integer> cols= new LinkedList<>();
HashMap<Integer, ArrayList<Integer>> map= new HashMap<>();
nodes.add(root);
cols.add(0);
int min=0, max=0;
while(!nodes.isEmpty()) {
int size= nodes.size();
for(int i=0; i<size; ++i) {
TreeNode node= nodes.remove();
int col=cols.remove();
map.computeIfAbsent(col, key-> new ArrayList<>() ).add( node.val);
if(node.left!=null) {
cols.add(col-1);
nodes.add(node.left);
min= Math.min(col-1, min);
}
if(node.right!=null) {
cols.add(col+1);
nodes.add(node.right);
max= Math.max(col+1, max);
}
}
}
for(int col=min; col<=max; col++) {
levels.add( map.get(col) );
}
System.out.println("\nVertical: "+levels);
return levels;
}
Raw
Depth.py
Maximum Depth: 104
Minimum Dept: 111
104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
#-----------------------bfs------------------------
if root:
return 1 + max( self.maxDepth(root.left), self.maxDepth(root.right) )
return 0
#-----------------------dfs-------------------------
#runtime complexity: O(n) space complexity: O(n)
if not root: return 0
ans= 0
nodes= [root]
while nodes:
nextNodes= []
ans += 1
for node in nodes:
if node.left: nextNodes.append(node.left)
if node.right: nextNodes.append(node.right)
nodes= nextNodes
return ans
111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
#runtime complexity: O(N) space complexity: O(N)
#bfs
if not root: return 0
ans= 0
nodes= [root]
while nodes:
nextNodes= []
ans += 1
for node in nodes:
if not node.left and not node.right: return ans
if node.left: nextNodes.append(node.left)
if node.right: nextNodes.append(node.right)
nodes= nextNodes
return ans
103. Binary Tree Zigzag Level Order Traversal
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
#--------------------------bfs----------------------------------------------------
if not root: return []
ans= []
nodes= [root]
depth= 0
while nodes:
nextNodes= []
level= []
depth+= 1
for node in nodes:
level= level+[node.val] if depth%2==1 else [node.val]+level
if node.left: nextNodes.append(node.left)
if node.right: nextNodes.append(node.right)
ans.append(level)
nodes= nextNodes
return ans
Raw
island.py
200. Number of Islands **
https://leetcode.com/problems/number-of-islands/description/
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def dfs(i, j):
if 0<=i<h and 0<=j<w and grid[i][j]=='1':
grid[i][j]=False
dfs(i+1,j)
dfs(i-1,j)
dfs(i,j+1)
dfs(i,j-1)
return True
def bfs(i, j):
nodes= [[i,j]]
ans= False
while nodes:
nextNodes= []
for node in nodes:
i,j= node
if 0<=i<h and 0<=j<w and grid[i][j]=='1':
ans= True
grid[i][j]=False
nextNodes.append([i+1, j])
nextNodes.append([i-1, j])
nextNodes.append([i, j+1])
nextNodes.append([i, j-1])
nodes= nextNodes
return ans
if not len(grid): return 0
h, w= len(grid), len(grid[0])
ans = 0
for i in range(h):
for j in range(w):
#ans += bfs(i, j)==True
ans += dfs(i, j)==True
return ans
Raw
word ladder.py
127. Word Ladder
https://leetcode.com/problems/word-ladder/
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
len_word = len(wordList[0])
wordList = set(wordList)
if endWord not in wordList: return 0
wordList.add(beginWord)
d = collections.defaultdict(list)
for word in wordList:
for i in range(len_word):
s = word[:i] + '_' + word[i+1:]
d[s].append(word)
visited = set(beginWord)
cnt = 1
nodes = [beginWord]
while nodes:
nextNodes = []
for node in nodes:
for i in range(len_word):
s = node[:i] + '_' + node[i+1:]
for neighbor in d[s]:
if neighbor not in visited:
if neighbor == endWord: return cnt + 1
visited.add(neighbor)
nextNodes.append(neighbor)
nodes = nextNodes
cnt += 1
return 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment