广度优先搜索算法(Breadth-First-Search,缩写为 BFS),是一种利用队列实现的搜索算法。简单来说,其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。
深度优先搜索算法(Depth-First-Search,缩写为 DFS),是一种利用递归实现的搜索算法。简单来说,其搜索过程和 “不撞南墙不回头” 类似。
BFS 的重点在于队列,而 DFS 的重点在于递归。这是它们的本质区别。
DFS 和 BFS 都是常用来遍历搜索树或图的算法。二叉树中的前序、中序和后序遍历都属于DFS,层次遍历属于BFS。DFS常用递归和栈来实现,BFS常用队列来实现。
BFS用queue (程序中用的deque,不用deque直接用普通队列一样的)
按BFS的方法遍历整个树,即用队列先后保存左右子节点,这样就可以一层一层的记录每个节点的val,输出到res中
利用了queue先进先出的特点,append时先左再右,这样pop时的顺序也是先左再右