Try   HackMD

No. 99 - Recover Binary Search Tree

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →


LeetCode 99 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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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 可以參考這篇的講解,其中也有實作 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)