二叉搜索树DFS共有三种遍历方式，分别为“前序遍历”、“中序遍历”与“后序遍历”。让我们先考虑以下一种简单的DFS算法：

1
void order(TreeNode *root) {
2
    if (root == nullptr)
3
        return;
4
    order(root->left);
5
    order(root->right);
6
}

显然地，该代码会尝试左侧优先遍历整个二叉树，具体模式如下：

让我们先给出这三种遍历方式的代码：

1
/* 前序遍历 */
2
void preOrder(TreeNode *root) {
3
    if (root == nullptr)
4
        return;
5
    // 访问优先级：根节点 -> 左子树 -> 右子树
6
    vec.push_back(root->val);
7
    preOrder(root->left);
8
    preOrder(root->right);
9
}
10

11
/* 中序遍历 */
12
void inOrder(TreeNode *root) {
13
    if (root == nullptr)
14
        return;
15
    // 访问优先级：左子树 -> 根节点 -> 右子树
16
    inOrder(root->left);
17
    vec.push_back(root->val);
18
    inOrder(root->right);
19
}
20

21
/* 后序遍历 */
22
void postOrder(TreeNode *root) {
23
    if (root == nullptr)
24
        return;
25
    // 访问优先级：左子树 -> 右子树 -> 根节点
26
    postOrder(root->left);
27
    postOrder(root->right);
28
    vec.push_back(root->val);
29
}

观察发现三者在代码上较为相似，区别仅体现在将节点数据存入列表时的语句位置略有不同。这说明三者的节点遍历逻辑是完全一致的，仅仅在节点数据存入顺序上存在差异。

让我们进一步对节点存入顺序进行分析，不难发现以下事实：

• 前序遍历采用数据优先的策略，因而到达每个节点后会直接存入对应数据。
• 中序遍历采用左侧优先的策略，因而到达每个节点的左侧叶节点 |1->2->4, 1->3->6| 后才会开始存入数据。
• 后序遍历采用遍历优先的策略，因而到达每个节点的叶节点后才会开始存入数据。

三者在宏观上体现为：

• 前序遍历存入数据顺序完全符合遍历顺序。
• 中序遍历存入数据顺序按左叶节点优先，遍历顺序为次存入数据。
• 后序遍历存入数据顺序按子节点优先，遍历顺序为次存入数据。

该二叉树DFS遍历顺序为： 1 -> 2 -> 4 -> 2 -> 5 -> 2 -> 1 -> 3 -> 6 -> 3 -> 7 -> 3 -> 1

• 前序遍历存入的顺序为： |1| -> |2| -> |4| -> 2 -> |5| -> 2 -> 1 -> |3| -> |6| -> 3 -> |7| -> 3 -> 1
• 中序遍历存入的顺序为： 1 -> 2 -> |4| -> |2| -> |5| -> 2 -> |1| -> |3| -> |6| -> 3 -> |7| -> 3 -> 1
• 后序遍历存入的顺序为： 1 -> 2 -> |4| -> 2 -> |5| -> |2| -> 1 -> 3 -> |6| -> 3 -> |7| -> |3| -> |1|

将回溯纳入考虑，记为井号： 该二叉树DFS遍历顺序为： 1 -> 2 -> 4 -# 2 -> 5 -# 2 -# 1 -> 3 -> 6 -# 3 -> 7 -# 3 -# 1

• 前序遍历存入的顺序为： |1| -> |2| -> |4| -# 2 -> |5| -# 2 -# 1 -> |3| -> |6| -# 3 -> |7| -# 3 -# 1
• 中序遍历存入的顺序为： 1 -> 2 -> |4| -# |2| -> |5| -# 2 -# |1| -> |3| -> |6| -# 3 -> |7| -# 3 -# 1
• 后序遍历存入的顺序为： 1 -> 2 -> |4| -# 2 -> |5| -# |2| -# 1 -> 3 -> |6| -# 3 -> |7| -# |3| -# |1|

观察发现：

• 前序遍历遇到新元素会直接存入列表
• 中序排列在抵达该节点的左叶节点后遇到新元素会直接存入列表
• 后序排列较为复杂，在抵达叶节点时直接存入，在左右子叶均抵达后回溯到达非叶节点时直接存入。

进行统一表述，可以得到：

• 三者在抵达叶节点时均会直接存入

面对新元素 |未存入数据的节点| 的策略：

• 前序遍历未抵达左侧全体叶节点、未抵达右侧全体叶节点时遇到新元素会直接存入列表
• 中序排列已抵达左侧全体叶节点、未抵达右侧全体叶节点时遇到新元素会直接存入列表
• 后序排列已抵达左侧全体叶节点、已抵达右侧全体叶节点时遇到新元素会直接存入列表