Recover Binary Search Tree

描述

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

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

分析

O(logn)空间的解法是，中序递归遍历，用两个指针存放在遍历过程中碰到的两处逆向的位置。

本题要求O(1)空间，只能用Morris中序遍历。

中序遍历，递归方式

  1. // Recover Binary Search Tree
  2. // 中序遍历,递归
  3. // 时间复杂度O(n)，空间复杂度O(logn)
  4. // 本代码仅仅是为了帮助理解题目
  5. class Solution {
  6. public:
  7.     void recoverTree(TreeNode *root) {
  8.         inOrder( root);
  9.         swap(p1->val, p2->val);
  10.     }
  11. private:
  12.     void inOrder(TreeNode *root) {
  13.         if ( root ==  nullptr ) return;
  14.         if ( root->left != nullptr ) inOrder(root->left);
  16.         if ( prev != nullptr && root->val < prev->val ) {
  17.             if ( p1 == nullptr) {
  18.                 p1 = prev;
  19.                 p2 = root;
  20.             } else {
  21.                 p2 = root;
  22.             }
  23.         }
  24.         prev = root;
  25.         if ( root->right != nullptr ) inOrder(root->right);
  26.     }
  27.     TreeNode *p1 = nullptr;
  28.     TreeNode *p2 = nullptr;
  29.     TreeNode *prev = nullptr;
  30. };

Morris中序遍历

  1. // Recover Binary Search Tree
  2. // Morris中序遍历，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     void recoverTree(TreeNode* root) {
  6.         pair<TreeNode*, TreeNode*> broken;
  7.         TreeNode* prev = nullptr;
  8.         TreeNode* cur = root;
  10.         while (cur != nullptr) {
  11.             if (cur->left == nullptr) {
  12.                 detect(broken, prev, cur);
  13.                 prev = cur;
  14.                 cur = cur->right;
  15.             } else {
  16.                 auto node = cur->left;
  18.                 while (node->right != nullptr && node->right != cur)
  19.                     node = node->right;
  21.                 if (node->right == nullptr) {
  22.                     node->right = cur;
  23.                     //prev = cur; 不能有这句！因为cur还没有被访问
  24.                     cur = cur->left;
  25.                 } else {
  26.                     detect(broken, prev, cur);
  27.                     node->right = nullptr;
  28.                     prev = cur;
  29.                     cur = cur->right;
  30.                 }
  31.             }
  32.         }
  34.         swap(broken.first->val, broken.second->val);
  35.     }
  37.     void detect(pair<TreeNode*, TreeNode*>& broken, TreeNode* prev,
  38.             TreeNode* current) {
  39.         if (prev != nullptr && prev->val > current->val) {
  40.             if (broken.first == nullptr) {
  41.                 broken.first = prev;
  42.             } //不能用else，例如 {0,1}，会导致最后 swap时second为nullptr，
  43.               //会 Runtime Error
  44.             broken.second = current;
  45.         }
  46.     }
  47. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/traversal/recover-binary-search-tree.html