我刚遇到这个问题，想知道我是否能想出一个正确的解决方案。问题涉及交换二叉树的两个节点，不仅按值，而且按节点。所以这意味着我们也必须改变右值和左值。
因此，可以说我们有一个类似于上图的二叉树。我最初的想法是对节点进行中序遍历，以便我可以展平树，然后交换元素，然后从交换的列表中重建树。所以从字面上看，解决方案是这样的
对于上面提到的树，中序遍历会生成一个这样的列表，
1,3,4,6,7,8,10,13,14。
现在我交换 8 和 13。
=> 1,3,4,6,7,13,10,8,14
但是这里的问题是，由于我现在在尝试重建时已将树展平，所以我无法这样做，因为我不知道各个节点的位置，例如特定节点是左子节点还是它是一个根。因此，从字面上看，树不能像最初使用交换节点时那样重新生成。
现在的问题是我是否可以修改我的遍历算法来保存每个节点的位置信息，以便当我交换元素并重建时，我想出与交换所需节点相同的二叉树？我们可以在中序遍历期间存储各个节点的状态/位置吗？
PS。我认识到进行后排序会使我的列表包含要交换的第一个和最后一个节点，但是需要交换的两个节点不一定位于根和最右边的元素，它可以是任意两个。
您的问题几乎没有歧义。您在 BST 中的示例中的树（尽管 BST 也是二叉树）和最终答案可能会破坏 BST 属性。我想这就是答案所需要的。如果我错了，请纠正我。
就答案而言，有两种解决方案。
一，我可以想到，就遍历和展平而言，您不能仅通过一次遍历来重新构建树。您需要 2 次遍历来构造一棵树。它可能是以下任何一种
因此，在 2 次遍历中的任何一个上进行交换并重新构建。那应该给出答案。
第二种解决方案是一个更好、更有效的解决方案，因为 Time Comp 是 O(n)。在这个方法中，对整个树进行遍历，得到两个候选节点的引用指针。一旦你有了引用，使用一个临时变量来交换信息。这种方法很复杂，但比以前的方法更节省空间和时间。
希望这不是硬件问题，如果是，请标记它！
例如：
4
2 6
1 3 5 7
这棵树的顺序遍历如下所示： Pre : 4 2 1 3 6 5 7 Inorder : 1 2 3 4 5 6 7
现在您知道 4 是这棵树的根（因为根被打印为 Preorder 的第一个元素）。现在基于 4 拆分遍历。
现在左子树变成了 Pre : 2 1 3 ; 顺序：1 2 3
并且右子树变为 Pre : 6 5 7 ；顺序：5 6 7
继续递归地这样做，这将是答案！