二叉树的遍历——DFS深度优先搜索——先（根）序遍历、中序遍历、后序遍历_二叉树的先根遍历和中根遍历

二叉树的深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

深度优先遍历主要有三种方式：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）。

1、区分先序遍历、中序遍历、后序遍历

这里的先、中、后是针对根结点的。并且总是先左后右。
先序遍历的访问顺序是：根节点、左子树、右子树（根、左、右）
中序遍历：左、根、右。后序遍历：左、右、根

其中隐藏了递归思想。如：先序遍历先访问根结点，然后访问左子树，对于这个左子树的访问，其顺序依然是根、左、右；当这个左子树访问完成后，访问右子树，对于这个右子树也一样，先访问根结点，然后访问左右子树。

例子

2、代码实现

先序遍历 中序遍历 后序遍历 只是在跟结点append进result列表的位置不同而已

测试结果

3、特点

三种遍历方法对结点访问的行进路线是一样的
下图中白色圆圈代表先序遍历、蓝色圆圈代表中序遍历、黑色圆圈代表后序遍历

4、时间复杂度分析

5、先序遍历中序遍历 或 后序遍历中序遍历 可以唯一确定一个二叉树

（1）先序遍历中序遍历唯一确定一个二叉树图示：

（2）先序遍历和后序遍历无法唯一确定一个二叉树

原因

1、丢失的结构信息：先序遍历和后序遍历都只涉及节点访问的顺序，而没有直接提供关于节点之间连接关系的信息。特别是，它们没有明确指出哪些节点是另一个节点的左子节点，哪些是右子节点。因此，即使我们知道节点的访问顺序，也无法仅凭此信息重建出唯一的树结构。

2、同构树的存在：有些不同的二叉树在进行先序遍历或后序遍历后，会得到相同的节点访问顺序。这些树称为同构树。同构树在结构上不同，但在特定的遍历方式下，它们的节点访问顺序却相同。