给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

 提示：

  • 树上节点的数目在范围 [2, 1000] 内

  • -231 <= Node.val <= 231 - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

思路

  • 中序遍历+数组判断不符合的两个节点

  • 优化：中序遍历时直接找到两个对应节点存储，遍历完后交换值

  • 终极优化：Morris遍历(降低空间复杂度)

代码

  • 中序遍历+数组判断不符合的两个节点

/**
 * 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 {
    //99. 恢复二叉搜索树
    public void recoverTree(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        recoverTreeDfs(root, list);
        int start = 0;
        int end = list.size() - 1;
        while (start < list.size()) {
            if (list.get(start) > list.get(start + 1)) {//找到第一个节点
                break;
            }
            start++;
        }
        while (end > 1) {
            if (list.get(end) < list.get(end - 1)) {//找到第二个节点
                break;
            }
            end--;
        }
        recoverTreeTask(root, list, start, end);//交换
    }

    private int index;

    private void recoverTreeDfs(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        recoverTreeDfs(root.left, list);
        list.add(root.val);
        recoverTreeDfs(root.right, list);
    }


    private void recoverTreeTask(TreeNode root, List<Integer> list, int start, int end) {
        if (root == null) {
            return;
        }
        recoverTreeTask(root.left, list, start, end);
        if (index == start) {
            root.val = list.get(end);
        } else if (index == end) {
            root.val = list.get(start);
        }
        index++;
        recoverTreeTask(root.right, list, start, end);
    }
}

  • 优化：中序遍历时直接找到两个对应节点存储，遍历完后交换值

/**
 * 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 {
    //99. 恢复二叉搜索树
    public void recoverTree(TreeNode root) {
        TreeNode[] nodes = new TreeNode[3];
        recoverTreeDfs(root, nodes);
        int temp = nodes[1].val;
        nodes[1].val = nodes[2].val;
        nodes[2].val = temp;
    }

    private void recoverTreeDfs(TreeNode root, TreeNode[] nodes) {
        if (root == null) {
            return;
        }
        recoverTreeDfs(root.left, nodes);
        if (null != nodes[0]) {
            if (nodes[0].val > root.val) {
                if (nodes[1] == null) {
                    nodes[1] = nodes[0];
                }
                nodes[2] = root;
            }
        }
        nodes[0] = root;
        recoverTreeDfs(root.right, nodes);
    }
}

  • 终极优化：Morris遍历(降低空间复杂度)

class Solution {
    //99. 恢复二叉搜索树
    public void recoverTree(TreeNode root) {
        TreeNode current = root;
        TreeNode prev = null;
        TreeNode first = null;
        TreeNode second = null;
        while (current != null) {
            if (current.left == null) {
                // 处理当前节点
                if (prev != null && prev.val > current.val) {
                    if (first == null) {
                        first = prev;
                    }
                    second = current;
                }
                prev = current;
                current = current.right;
            } else {
                // 找到前驱节点（左子树的最右节点）
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                // Morris精髓：根据中序遍历顺序不断链接父节点的右子树，整个操作相当于将原树转化为只有右节点的单链表
                if (predecessor.right == null) {
                    // 建立临时链接
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // 断开临时链接并处理当前节点
                    predecessor.right = null;
                    if (prev != null && prev.val > current.val) {
                        if (first == null) {
                            first = prev;
                        }
                        second = current;
                    }
                    prev = current;
                    current = current.right;
                }
            }
        }
        // 交换两个错误节点的值
        if (first != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }
}