可以结合一下 [86. Validate Binary Search Tree](../86. Validate Binary Search Tree), 至少要清楚 BST 的概念。

就本质而言，BST 的核心特质就是有序。何谓有序？最直接的方式就是将 BST 按照 Inorder 的遍历思想下落，落下来的序列是有序的。

3 /
1 5 / \ /
0 2 4 6

0 1234 5 6 -> ordered

回到这道题，让我们 recover 这个 BST, 是因为某一次的 swap 出了错，关键是要理解 swap 出了什么错。提到 two elements, 再结合上面温习的基础概念，可以推测出，这两个 elements 待在了不该待的位置。我们 recover 的目的便是将这两个放错地方的 elements 对调过来。

题目又说了，不能动 BST 的结构，那么所谓的对调，便是针对值的对调。所以大致可以分为两个步骤：

find two error elements.
swap two elements' values.

对于第二步，非常 easy, 我们有 std::swap. 但是对于第一条，我们该如何查找，首先就应该想到是 DFS.

在 [77. Construct Binary Tree from Inorder and Postorder Traversal](../77. Construct Binary Tree from Inorder and Postorder Traversal) 中我们曾总结，对于二叉树来说，DFS 有三种方式：

先序遍历（先根遍历）
中序遍历（中根遍历）
后续遍历（后根遍历）

我们这道题的目的是查出哪里违反了 BST 的次序，正如最开始所说，最直接的方式是通过中序遍历的方式查看序列是否有序。那么我们显然应该选择中序遍历的 DFS 方法。

写出最简单的中序遍历：

void InorderTraversal(TreeNode *root)
{
    if (root == NULL) return;
    InorderTraversal(root->left);
    cout << root->val << " ";
    InorderTraversal(root->right);
}

然后，考虑我们的需求，要找到两个元素，而找的条件是次序不符，如何叫次序不符？先遍历出来的元素 > 后遍历出来的元素，即为不符。

显然，我们需要三个指针来协助：first, second, prev, 分别代表第一个元素，第二个元素，上一个元素。

当出现 prev->val > root->val 时，表示找到不符的元素。若是第一个，则为 first. 无论是不是，都将当前的 root 赋给 second, 因为可能会出现仅有两个节点的情况（仅仅遍历一次，second 无法获取应得的值）. 这部分逻辑为：

if (first == NULL) first = prev;
second = root;

然后，便没有太多可说的了。总体来说，本题难度不大。