题解：找到二叉搜索树中两个错误的节点
原文中文，约1200字，阅读约需3分钟。
📝
内容提要
本文讨论了如何在二叉搜索树中找到两个错误的节点。由于节点位置调换，树不再是有效的二叉搜索树。通过中序遍历，可以识别出降序的节点，从而确定错误节点。如果两个节点相邻，则直接找到；如果不相邻，则会出现两次降序，分别对应两个错误节点。使用Morris遍历法，时间复杂度为O(n)，空间复杂度为O(1)。
🎯
关键要点
-
二叉树原本是二叉搜索树，但由于两个节点调换位置，导致树不再有效。
-
中序遍历可以识别出降序的节点，从而确定错误节点。
-
如果两个错误节点相邻，则直接找到；如果不相邻，则会出现两次降序。
-
第一次降序时，前面的较大元素是错误节点；第二次降序时，后面的较小元素是错误节点。
-
使用Morris遍历法，时间复杂度为O(n)，空间复杂度为O(1)。
❓
延伸问答
如何在二叉搜索树中找到两个错误的节点？
通过中序遍历识别降序的节点，从而确定错误节点。如果两个节点相邻，直接找到；如果不相邻，则会出现两次降序，分别对应两个错误节点。
中序遍历在识别错误节点中有什么作用？
中序遍历可以识别出降序的节点，降序的出现表明树中存在错误节点。
如果两个错误节点不相邻，如何识别它们？
如果两个错误节点不相邻，会出现两次降序，第一次降序时前面的较大元素是错误节点，第二次降序时后面的较小元素是错误节点。
Morris遍历法的时间和空间复杂度是多少？
Morris遍历法的时间复杂度为O(n)，空间复杂度为O(1)。
为什么二叉搜索树会变得无效？
二叉搜索树变得无效是因为其中两个节点的位置被调换了。
如何判断两个节点是否相邻？
如果在中序遍历中只出现一次降序，则这两个节点是相邻的；如果出现两次降序，则它们不相邻。
🏷️
