99. 恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]1/3\2输出: [3,1,null,null,2]3/1\2
示例 2:
输入: [3,1,4,null,null,2]3/ \ 1 4/2输出: [2,1,4,null,null,3]2/ \ 1 4/3
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
空间复杂度为O(n)的解法
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {// 上一次中序遍历过的节点private TreeNode prev;// 第一个错误的节点private TreeNode first;// 第二个错误的节点private TreeNode second;public void recoverTree(TreeNode root) {findWrongNodes(root);// 交换两个错误节点的值int tmp = first.val;first.val = second.val;second.val = tmp;}private void findWrongNodes(TreeNode root) {if (root == null) return;findWrongNodes(root.left);// 出现了逆序对if (prev != null && prev.val > root.val) {// 第二个错误节点:最后一个逆序对中较小的那个节点second = root;// 第一个错误节点: 第一个逆序对中较大的那个节点if (first != null) return;first = prev;}prev = root;findWrongNodes(root.right);}}