一定要早日上岸鸭 · July 28, 2021 0

BFS && DFS 模板:

广度优先搜索BFS:

def bfs(seed): q = queue() q.put(seed) while not q.empty(): now = q.get() for 所有和 now 相邻的节点 x: q.put(x)

深度优先搜索DFS:

def dfs(seed): if 递归出口(seed): return for 所有相邻节点x: dfs(x)

BFS: Java 双端队列的实现:

class Solution { ArrayDeque<TreeNode> dq = new ArrayDeque<TreeNode>(); List<List<Integer>> ret = new ArrayList<List<Integer>>(); public void bfs(TreeNode root){ if(root==null) return; dq.addLast(root); while(!dq.isEmpty()){ int size = dq.size(); List<Integer> nodes = new ArrayList<Integer>(); while(size>0){ TreeNode res = dq.pollFirst(); nodes.add(res.val); if(res.left!=null) dq.addLast(res.left); if(res.right!=null) dq.addLast(res.right); size--; } ret.add(nodes); } } public List<List<Integer>> levelOrder(TreeNode root) { bfs(root); return ret; } }