DFS

递归写法

  1. def dfs(node, visited):
  2.     if node in visited: # terminator
  3.         # already visited 
  4.         return  
  5.     visited.add(node) 
  6.     # process current node here. 
  7.     ...
  8.     for next_node in node.children(): 
  9.         if not next_node in visited: 
  10.             dfs(next_node, visited)

非递归写法
def DFS(self, tree):

  1. def DFS(self, tree): 
  3.     if tree.root is None: 
  4.         return [] 
  6.     visited, stack = [], [tree.root]
  8.     while stack: 
  9.         node = stack.pop() 
  10.         visited.add(node)
  12.         process (node) 
  13.         nodes = generate_related_nodes(node) 
  14.         stack.push(nodes) 
  16.     # other processing work 
  17.     ...

BFS

  1. const bfs = (root) => {  
  2.   let result = [], queue = [root]  
  3.   while (queue.length > 0) {    
  4.     let level = [], n = queue.length    
  5.     for (let i = 0; i < n; i++) {      
  6.       let node = queue.pop()      
  7.       level.push(node.val)       
  8.       if (node.left) queue.unshift(node.left)      
  9.       if (node.right) queue.unshift(node.right)    
  10.     }   
  11.     result.push(level)  
  12.   }  
  13.   return result
  14. };