RecoveringaBinarySearchTree题目描述：给定一棵二叉搜索树的根节点root，错误地交换了树中的两个节点。请在不改变其结构的情况下恢复这棵树。高级：解决方案易于实现，空间复杂度为O(n)。你能想出一个只使用恒定空间的解决方案吗？例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。方案一：递归法首先，通过中序遍历得到二叉搜索树的所有节点allNodes。一般情况下，如果没有错误交换节点，allNodes的所有节点应该按升序排列，所以找出交换的2个节点；从后往前遍历allNodes，找到第一个值小于前一个值的节点，即第一个错的节点high；从high-1开始，向前遍历allNodes，找到第一个值小于high的节点，最小节点为low，low+1位置的节点为第二个错误的节点；交换低节点和高节点的值来恢复树。importjava.util.ArrayList;importjava.util.List;publicclassLeetCode_099{publicstaticvoidrecoverTree(TreeNoderoot){ListallNodes=inOrder(root);int高=-1,低=-1;for(inti=allNodes.size()-1;i>=1;i--){//找到上面要交换的节点if(allNodes.get(i).val=0;low--){if(allNodes.get(low).valinOrder(TreeNoderoot){Listnodes=newArrayList<>();如果（root！=null）{nodes.addAll（inOrder（root.left））;节点。添加（根）；nodes.addAll(有序(root.right));}返回节点；}publicstaticvoidmain(String[]args){TreeNoderoot=newTreeNode(3);root.left=newTreeNode(1);root.right=newTreeNode(4);root.right.left=newTreeNode(2);恢复树（根）；System.out.println("恢复前");根打印（）；System.out.println();System.out.println("恢复后");根打印（）；}}【每日留言】感谢你不离不弃，让我知道还有人爱我，感谢你的支持。不管我今天多么沮丧，我仍然会勇敢地生活。
