，我们熟悉了树、二叉树、二叉搜索树的基本概念，并做了对应的实战题目：树，二叉树，二叉搜索树&&实战练习今天继续树的话题。本文主要内容包括：理论：树遍历理论：广度优先搜索理论：深度优先搜索理论：树级遍历实践：Leetcode题目钻树是一种比较常见的数据结构，在面试中也很常见.熟悉树的前中后序遍历，只是为了让大家明白树的遍历可以有不同的顺序，实际应用比较少，意义不大，但是作为基础，还是需要学习这部分。基本上，真正的遍历还是要靠深度优先和广度优先遍历。话不多说，让我们进入正文。文本树的前中后序遍历三种遍历顺序非常好记：preorder:rootleftandrightinorder:leftrootrightpostorder:leftandrightrootpreordertraversal如图所示，这样一个二叉树前序遍历，先访问根节点，再访问左子树，再访问右子树。遍历的结果是：A,B,D,E,C,F,G中序遍历先访问左子树，再访问根，再访问右子树。遍历的结果是：D,B,E,A,F,C,G后序遍历先访问左子树，再访问右子树，再访问根。遍历的结果是：D,E,B,F,G,C,A前中后序遍历的代码实现-medium如果你对这三种遍历非常熟悉，在遇到问题的时候比如验证二叉查找树的时候，就知道可以利用中序遍历的特性来验证。我们来看看这三个遍历的逻辑实现。这里借用社区大佬的Python实现，很优雅：Leetcode也有这三种遍历题目，因为不是本文的重点，就简单用递归实现：144先序的简单实现traversal-medium给定一个二叉树，返回它的_preorder_traversal。输入：[1,null,2,3]1\2/3输出：[1,2,3]代码实现：varpreorderTraversal=function(root){varstack=[]functionhelper(root){if(!root)returnstack.push(root.val)root.left&&helper(root.left)root.right&&helper(root.right)}helper(root)returnstack}94:中序遍历的简单实现给定一个二叉树，返回其顺序遍历。示例：输入：[1,null,2,3]1\2/3输出：[1,3,2]代码实现：varinorderTraversal=function(root){varstack=[]functionhelper(root){if(!root)returnroot.left&&helper(root.left)stack.push(root.val)root.right&&helper(root.right)}helper(root)returnstack};145:后序遍历的简单实现——hard给定一个二叉树，返回它的后序遍历。例子：输入：[1,null,2,3]1\2/3输出：[3,2,1]代码实现：varpostorderTraversal=function(root){varstack=[]functionhelper(root){if(!root)returnroot.left&&helper(root.left)root.right&&helper(root.right)stack.push(root.val)}helper(root)returnstack}第1部分总结上面的部分，我们是熟悉了了解了二叉树的三种遍历方式，熟悉了三个实际问题之后，我们就来正式接触今天的主角：BFS&DFS。广度优先搜索广度优先搜索（Breadth-First-Search），简称BFS，是一种比较常见的二叉树搜索方法。先说说为什么会出现这种搜索方式。比如在我们的生活中，我们需要在一个大的集合中找到一个特定的元素，它可能是一个状态集，也可能是一些树，或者图。比如我们要找箭头所指的点，应该怎么找呢？我们最直观的反应就是一层层往前，一层层往下找。最符合我们思维方式的搜索方法是广度优先搜索。我们来看看这个方法具体是怎么搜索的。首先，访问根节点1。接下来依次访问1的子节点，即节点2、3、4，以此类推。就像水波一样，一层层往前推进，更符合人类的思维习惯。BFS的实现思路也比较直观：从1开始，依次将子节点放入队列，遍历的节点依次放入队列，队列先进先出，从而达到层次遍历的效果。BFS的实现BFS伪代码实现：为了避免重复搜索，引入了一个权重判断集来记录搜索到的节点。我们看一个具体的例子：有如下html结构，要求分层打印出每个节点：
