LeetCode 99. 恢复二叉搜索树思路BST 的中序遍历是严格递增的。若有两个节点被错误交换中序序列中会出现「逆序对」· 交换的是相邻节点如 1,3,2,4 → 只有 1 处逆序 32first 3second 2· 交换的是不相邻节点如 1,4,3,2,5 → 有 2 处逆序 43 和 32first 取第一处的较大值 4second 取第二处的较小值 2找到 first 和 second 后交换它们的值即可。解法一中序遍历O(n) 时间O(h) 空间classSolution{privateTreeNodefirstnull;privateTreeNodesecondnull;privateTreeNodeprevnull;publicvoidrecoverTree(TreeNoderoot){inorder(root);// 交换两个节点的值inttmpfirst.val;first.valsecond.val;second.valtmp;}privatevoidinorder(TreeNodenode){if(nodenull)return;inorder(node.left);if(prev!nullprev.valnode.val){if(firstnull)firstprev;// 第一次逆序记录较大的节点secondnode;// 每次逆序都更新 second较小节点}prevnode;inorder(node.right);}}解法二Morris 中序遍历O(n) 时间O(1) 空间用 Morris 遍历可以在不使用额外栈/递归的情况下完成中序遍历把空间降到 O(1)。classSolution{publicvoidrecoverTree(TreeNoderoot){TreeNodefirstnull,secondnull,prevnull;TreeNodecurrroot;while(curr!null){if(curr.leftnull){// 访问 currif(prev!nullprev.valcurr.val){if(firstnull)firstprev;secondcurr;}prevcurr;currcurr.right;}else{// 找左子树的最右节点中序前驱TreeNodepredcurr.left;while(pred.right!nullpred.right!curr){predpred.right;}if(pred.rightnull){pred.rightcurr;// 建立线索currcurr.left;}else{pred.rightnull;// 断开线索// 访问 currif(prev!nullprev.valcurr.val){if(firstnull)firstprev;secondcurr;}prevcurr;currcurr.right;}}}// 交换inttmpfirst.val;first.valsecond.val;second.valtmp;}}节点定义题目已给出publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}复杂度对比解法 时间 空间 特点递归中序遍历 O(n) O(h) 代码简洁迭代中序遍历 O(n) O(h) 显式用栈Morris 遍历 O(n) O(1) 面试加分项关键点提醒first 只在第一次逆序时赋值之后不再改变。second 每次都更新这样才能覆盖相邻交换只逆序一次和非相邻交换逆序两次两种情况。遍历过程中不要真的交换节点指针交换 val 最省事题目也允许只修改值。