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.
Example 2.
本題的目的是要找出 BST 中被置換的兩個 nodes 並且把他們還原到原本位置。因為 BST 的 nodes 之間是有大小關係,只要有 nodes 被置就會違反 BST 的規則,所以我們要做的就是去比對 node 之間的大小關係。
本題是用 inorder traversal 的方式來解,我們這次不用 recursive 或把 node 存到 stack 用 iterative 的方法來解而是使用 Morris traversal 的方式來解,這樣可以達到不使用 stack 來做 inorder traversal 使得空間複雜度只要 。
我們知道 BST 的 inorder traversal 其實就是把 BST 的 nodes 從小到大排列出來。假設一個 BST,把它攤平後會是如下的數列:
我們如果把 2 跟 6 置換會變成:
因為 inorder traversal 其實就是從左到右的走訪,當走訪到 3 的時候我們會發現它比前面的 6 還要小,代表 6 是有問題的,當走訪到 2 的時候我們會發現它比前面的 5 還要小,這代表 2 是有問題的。
根據上面的描述我們可以知道,對 BST 做 inorder traversal 時,第一次遇到比對錯誤,錯的是前面的值,而第二次比對錯誤,錯的是當前走訪的值。而我們可以寫出下面的比對方法,其中 node
表示前一個走訪的 node,cur
表示當前的 node,fault1
表示第一次錯的 node,fault2
表示第二次錯的 node。
這個比對方法其實就是在 inorder traversal 走訪完左子樹走訪父節點的時候要做的比對。
如何用 Morris traversal 來做 inorder traversal 可以參考這篇的講解,其中也有實作 preorder 跟 postorder traversal。
由於 Morris traversal 不會用到 stack 來存走訪的 node,也就是說需要另外想辦法知道每次走訪到的 node 其 parent 是誰,所以 Morris traversal 的概念就是把當前 node 的左子樹將會走訪到的最後的 node 指向 right child 的指標指回當前的 node,這樣當左子樹走訪完了就可以回到當前 node 接著走訪右子樹。
完整的程式碼如下:
時間複雜度為 ,但若詳細算的話會需要 。Morris traversal 實現 inorder traversal 除了單純的走訪完整個 tree,還需要把每一個左子樹走訪的最後一個 node 找出來,這其實也要走訪所有的 nodes 一遍才能找到,所以實際上會把 tree 走訪兩遍。
因為 Morris traversal 的方法不需要任何 stack 來存之前走訪過的 node 就可以找到 parent 所以空間複雜度為 。