数据结构与算法系列 - 深度优先和广度优先( 三 ) 本文作者：何建辉（公众号：org_yijiao

就比如说它开始刚进来的话，传的是 root 的话， root 就会先放到 visited 里面，表示 root 已经被 visit,被 visited之后就从 root.childern里面找 next_node ，所有它的next_node都没有被访问过的，所以它就会先访问最左边的这个结点，这里注意当它最左边这个结点先拿出来了，判断没有在 visited里面，因为除了 root之外其他结点都没有被 visited过，那么没有的话它就直接调dfs ， next_node 就是把最左边结点放进去，再把 visited也一起放进去。
递归调用的一个特殊，它不会等这个循环跑完，它就直接推进到下一层了，也就是当前梦境的话这里写了一层循环，但是在第一层循环的时候，我就要开始下钻到新的一层梦境里面去了。

图的遍历顺序

文章插图
广度优先搜索（BFS）广度优先遍历它就不再是用递归也不再是用栈了，而是用所谓的队列。你可以把它想象成一个水滴，滴到1这个位置，然后它的水波纹一层一层一层扩散出去就行了。

文章插图
两者对比

文章插图
BFS代码模板

//Javapublic class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}public List> levelOrder(TreeNode root) {List> allResults = new ArrayList<>();if (root == null) {return allResults;}Queue nodes = new LinkedList<>();nodes.add(root);while (!nodes.isEmpty()) {int size = nodes.size();List results = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = nodes.poll();results.add(node.val);if (node.left != null) {nodes.add(node.left);}if (node.right != null) {nodes.add(node.right);}}allResults.add(results);}return allResults;}

# Pythondef BFS(graph, start, end):visited = set()queue = []queue.append([start])while queue:node = queue.pop()visited.add(node)process(node)nodes = generate_related_nodes(node)queue.push(nodes)# other processing work...

// C/C++void bfs(Node* root) {map visited;if(!root) return ;queue queueNode;queueNode.push(root);while (!queueNode.empty()) {Node* node = queueNode.top();queueNode.pop();if (visited.count(node->val)) continue;visited[node->val] = 1;for (int i = 0; i < node->children.size(); ++i) {queueNode.push(node->children[i]);}}return ;}

//JavaScriptconst bfs = (root) => {let result = [], queue = [root]while (queue.length > 0) {let level = [], n = queue.lengthfor (let i = 0; i < n; i++) {let node = queue.pop()level.push(node.val)if (node.left) queue.unshift(node.left)if (node.right) queue.unshift(node.right)}result.push(level)}return result};

【数据结构与算法系列 - 深度优先和广度优先】文章持续更新，可以微信搜一搜「一角钱技术」第一时间阅读，本文 GitHub org_hejianhui/JavaStudy 已经收录，欢迎 Star 。