题目

You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Example 1:

image.png

  1. Input: root = [1,3,null,null,2]
  2. Output: [3,1,null,null,2]
  3. Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

image.png

  1. Input: root = [3,1,4,null,null,2]
  2. Output: [2,1,4,null,null,3]
  3. Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

  • The number of nodes in the tree is in the range [2, 1000].
  • -2^31 <= Node.val <= 2^31 - 1

题意

给定一个BST，其中有两个结点的值互换了导致这个BST不符合定义。要求找到这两个结点并处理使满足BST的性质，同时不能改变树的结构。

思路

BST的性质：中序遍历得到一个单调递增的序列。

最简单的O(N)空间的方法是先用中序遍历得到序列，找到互换了的两个结点，再将它们换回来。

O(1)空间方法：不能使用常规的递归或栈的方法进行中序遍历，改用Morris遍历，中途找到互换的两个结点。

代码实现

Java

中序遍历 - O(N)空间

  1. class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.         List<TreeNode> nodes = new ArrayList<>();
  4.         inorder(root, nodes);
  5.         TreeNode A = null, B = null;
  7.         for (int i = 1; i < nodes.size(); i++) {
  8.             if (nodes.get(i).val < nodes.get(i - 1).val) {
  9.                 if (A == null) {
  10.                     A = nodes.get(i - 1);
  11.                 }
  12.                 B = nodes.get(i);
  13.             }
  14.         }
  16.         int tmp = A.val;
  17.         A.val = B.val;
  18.         B.val = tmp;
  19.     }
  21.     private void inorder(TreeNode root, List<TreeNode> nodes) {
  22.         if (root == null) {
  23.             return;
  24.         }
  26.         inorder(root.left, nodes);
  27.         nodes.add(root);
  28.         inorder(root.right, nodes);
  29.     }
  30. }

Morris遍历 - O(1)空间

  1. class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.         TreeNode A = null, B = null;
  4.         TreeNode pre = null;
  6.         while (root != null) {
  7.             if (root.left != null) {
  8.                 TreeNode node = root.left;
  9.                 while (node.right != null && node.right != root) {
  10.                     node = node.right;
  11.                 }
  12.                 if (node.right == null) {
  13.                     node.right = root;
  14.                     root = root.left;
  15.                     continue;
  16.                 } else {
  17.                     node.right = null;
  18.                 }
  19.             }
  20.             if (pre != null && root.val < pre.val) {
  21.                 if (A == null) {
  22.                     A = pre;
  23.                 }
  24.                 B = root;
  25.             }
  26.             pre = root;
  27.             root = root.right;
  28.         }
  30.         int tmp = A.val;
  31.         A.val = B.val;
  32.         B.val = tmp;
  33.     }
  34. }