No. 99 - Recover Binary Search Tree
====


---

## [LeetCode 99 -- Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)

### 題目描述

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.

Example 1.

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

Example 2.

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

---

本題的目的是要找出 BST 中被置換的兩個 nodes 並且把他們還原到原本位置。因為 BST 的 nodes 之間是有大小關係，只要有 nodes 被置就會違反 BST 的規則，所以我們要做的就是去比對 node 之間的大小關係。

本題是用 inorder traversal 的方式來解，我們這次不用 recursive 或把 node 存到 stack 用 iterative 的方法來解而是使用 Morris traversal 的方式來解，這樣可以達到不使用 stack 來做 inorder traversal 使得空間複雜度只要 $O(1)$。

### 解法 - Morris Traversal

我們知道 BST 的 inorder traversal 其實就是把 BST 的 nodes 從小到大排列出來。假設一個 BST，把它攤平後會是如下的數列:

1|2|3|4|5|6|7

我們如果把 2 跟 6 置換會變成:

1|6|3|4|5|2|7

因為 inorder traversal 其實就是從左到右的走訪，當走訪到 3 的時候我們會發現它比前面的 6 還要小，代表 6 是有問題的，當走訪到 2 的時候我們會發現它比前面的 5 還要小，這代表 2 是有問題的。

根據上面的描述我們可以知道，對 BST 做 inorder traversal 時，第一次遇到比對錯誤，錯的是前面的值，而第二次比對錯誤，錯的是當前走訪的值。而我們可以寫出下面的比對方法，其中 `node` 表示前一個走訪的 node，`cur` 表示當前的 node，`fault1` 表示第一次錯的 node，`fault2` 表示第二次錯的 node。

if (node->val > cur->val) {
  if (!fault1)
    fault1 = node;
  fault2 = cur;
}

這個比對方法其實就是在 inorder traversal 走訪完左子樹走訪父節點的時候要做的比對。

如何用 Morris traversal 來做 inorder traversal 可以參考[**這篇**](https://www.itread01.com/content/1545897069.html)的講解，其中也有實作 preorder 跟 postorder traversal。

由於 Morris traversal 不會用到 stack 來存走訪的 node，也就是說需要另外想辦法知道每次走訪到的 node 其 parent 是誰，所以 Morris traversal 的概念就是把當前 node 的左子樹將會走訪到的最後的 node 指向 right child 的指標指回當前的 node，這樣當左子樹走訪完了就可以回到當前 node 接著走訪右子樹。

完整的程式碼如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  void recoverTree(TreeNode* root) {
    TreeNode *cur = root;
    TreeNode *node = nullptr;
    TreeNode *prev = nullptr;
    TreeNode *fault1 = nullptr;
    TreeNode *fault2 = nullptr;
    // use morris traversal to implement inorder traversal
    while (cur) {
      if (!cur->left) {
      // 左子樹走訪完了
        if (node && node->val > cur->val) {
          if (!fault1)
            fault1 = node;
          fault2 = cur;
        }
        node = cur;
        cur = cur->right;
      }
      else {
        prev = cur->left;
        // 尋找左子樹走訪到最後的 node 並將其指向 right child 的指標連回當前 node
        // 若已經有連回當前 node 代表左子樹已經走訪完
        while (prev->right && prev->right != cur)
          prev = prev->right;
        if (!prev->right) {
        // 第一次找到左子樹走訪完的最後一個 node
          prev->right = cur;
          cur = cur->left;
        }
        else {
        // 左子樹走訪完了
          prev->right = nullptr;
          if (node && node->val > cur->val) {
            if (!fault1)
              fault1 = node;
            fault2 = cur;
          }
          node = cur;
          cur = cur->right;
        }
      }
    }
    if (fault1)
      swap(fault1->val, fault2->val);
  }
};

### 複雜度分析

時間複雜度為 $O(N)$，但若詳細算的話會需要 $O(2N)$。Morris traversal 實現 inorder traversal 除了單純的走訪完整個 tree，還需要把每一個左子樹走訪的最後一個 node 找出來，這其實也要走訪所有的 nodes 一遍才能找到，所以實際上會把 tree 走訪兩遍。

因為 Morris traversal 的方法不需要任何 stack 來存之前走訪過的 node 就可以找到 parent 所以空間複雜度為 $O(1)$。