99. 恢復(fù)二叉搜索樹
題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/recover-binary-search-tree
題目
二叉搜索樹中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。
請?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹。
示例 1:
輸入: [1,3,null,null,2]
1
/
3
\
2
輸出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
輸入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
輸出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
進(jìn)階:
- 使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。
- 你能想出一個(gè)只使用常數(shù)空間的解決方案嗎？
解題思路
思路：中序遍歷（遞歸），Morris算法
題目中說明，二叉搜索樹中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換，需要在不改變結(jié)構(gòu)的情況下恢復(fù)二叉搜索樹。
我們知道，使用中序遍歷二叉搜索樹時(shí)，得到的序列必然是遞增的。如果二叉搜索樹的節(jié)點(diǎn)被錯(cuò)誤交換，那么使用中序遍歷，就能夠定位到錯(cuò)誤的節(jié)點(diǎn)。
假設(shè)有一個(gè)遞增的序列 [1, 2, 3, 4]，如果我們交換相鄰的位置，比如 2 和 3，那么序列就會(huì)變?yōu)?[1, 3, 2, 4]。此時(shí)，這里會(huì)出現(xiàn)一處錯(cuò)誤點(diǎn)，因?yàn)?3 > 2 不滿足序列遞增。如果我們交換不相鄰的位置，例如 1 和 4，那么序列就會(huì)變?yōu)?[4, 2, 3, 1]，此時(shí)，會(huì)出現(xiàn)兩個(gè)錯(cuò)誤點(diǎn)，4 > 2 和 3 > 1 不滿足序列遞增。
這里，我們可以判斷，當(dāng)兩個(gè)節(jié)點(diǎn)被錯(cuò)誤交換時(shí)，最多會(huì)產(chǎn)生兩處錯(cuò)誤。
這里額外提及下，因?yàn)榍懊娼o的例子，是先給定的遞增序列，我們假設(shè)取交換兩個(gè)節(jié)點(diǎn)。但如果給的是已經(jīng)交換的節(jié)點(diǎn)，如何將節(jié)點(diǎn)恢復(fù)至正確的位置。從上面假設(shè)的分析中，我們可以看到，如果是相鄰的節(jié)點(diǎn)被交換，那么我們只要再次交換兩個(gè)節(jié)點(diǎn)即可；但如果不是相鄰節(jié)點(diǎn)被交換，我們可以發(fā)現(xiàn)，兩處錯(cuò)誤點(diǎn)，只要將前面第一處錯(cuò)誤的左邊節(jié)點(diǎn)，與后面第二處錯(cuò)誤的右邊節(jié)點(diǎn)交換，即可恢復(fù)。
在這里，我們能直接想到的就是，利用一個(gè)數(shù)組，去存儲(chǔ)使用中序遍歷二叉搜索樹的值序列，只要能夠找到錯(cuò)誤的地方，就能夠?qū)⑵涓?/p>
中序遍歷（遞歸）
但這里，我們不使用額外的數(shù)組去存儲(chǔ)使用中序遍歷二叉搜索樹的值序列。因?yàn)榍懊娓鶕?jù)分析能夠判斷，當(dāng)兩個(gè)節(jié)點(diǎn)被錯(cuò)誤交換，最多會(huì)出現(xiàn)兩個(gè)錯(cuò)誤。那么我們只要關(guān)心中序遍歷的值序列每個(gè)相鄰的位置大小是否不對。下面是具體的算法（使用中序遍歷訪問）：
- 在遍歷訪問的過程中，用變量 pre_node 記錄當(dāng)前遍歷的最后一個(gè)節(jié)點(diǎn)。
- 當(dāng)進(jìn)行下個(gè)節(jié)點(diǎn)的遍歷時(shí)，用當(dāng)前節(jié)點(diǎn)的值與 pre_node 節(jié)點(diǎn)的值進(jìn)行比較。如果 pre_node.val >= cur_node.val，也就說明當(dāng)前位置出錯(cuò)。
- 繼續(xù)向下遍歷，若能找到第二處位置時(shí)，可以直接結(jié)束遍歷。
- 當(dāng)確定錯(cuò)誤的位置時(shí)，將節(jié)點(diǎn)值進(jìn)行交換。
在這里，我們用遞歸來實(shí)現(xiàn)這個(gè)算法。具體代碼見【代碼實(shí)現(xiàn) # 中序遍歷（遞歸）】
注意： 這個(gè)算法，在最差的情況下，也就是需要交換的位置出現(xiàn)在樹的最右側(cè)的葉子節(jié)點(diǎn)中，那么這個(gè)算法同樣還是會(huì)遍歷整個(gè)二叉搜索樹。
Morris 算法
在題目進(jìn)階處提及，是否能夠?qū)崿F(xiàn)常數(shù)時(shí)間復(fù)雜度的算法。在官方題解中提及的就是 Morris 算法，并且也進(jìn)一步描述了這個(gè)算法的信息。如果有興趣了解的話，可以從下方的鏈接入口繼續(xù)了解。
那么在這里，筆者就僅使用 Morris 的思想去嘗試解決該問題，就不再額外展開描述。
具體的代碼見【代碼實(shí)現(xiàn) # Morris 算法】
代碼實(shí)現(xiàn)
# 中序遍歷（遞歸）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
# 用 pre_node 記錄遍歷的最后一個(gè)節(jié)點(diǎn)
self.pre_node = TreeNode(float('-inf'))
# 用來標(biāo)記兩個(gè)錯(cuò)誤
self.first_error_node = None
self.second_error_node = None
self.count = 0
def in_order(root):
if not root:
return None
in_order(root.left)
# 比較 pre_node 值與當(dāng)前節(jié)點(diǎn)的值
if self.pre_node.val >= root.val and self.first_error_node == None:
# 如果 pre_node >= root.val 表示此處出錯(cuò),進(jìn)行記錄
self.first_error_node = self.pre_node
if self.pre_node.val >= root.val and self.first_error_node:
# 這里標(biāo)記第二處錯(cuò)誤，無論是出現(xiàn)一次錯(cuò)誤還是兩次錯(cuò)誤都適用
self.second_error_node = root
# 出現(xiàn)兩次可以終止
self.count += 1
if self.count == 2:
return
# 維護(hù) pre_node
self.pre_node = root
in_order(root.right)
in_order(root)
# 交換節(jié)點(diǎn)
self.first_error_node.val, self.second_error_node.val = self.second_error_node.val, self.first_error_node.val
# Morris 算法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
first_error = None
second_error = None
pre_node = TreeNode(float('-inf'))
predecessor = None
while root:
if root.left:
predecessor = root.left
# 當(dāng)節(jié)點(diǎn)有左孩子時(shí)，找到當(dāng)前節(jié)點(diǎn)的最右的節(jié)點(diǎn)
while predecessor.right and predecessor.right != root:
predecessor = predecessor.right
# 如果 predecessor 節(jié)點(diǎn)的右孩子為 None，將右指針指向 root，然后遍歷左子樹
if predecessor.right == None:
predecessor.right = root
root = root.left
# 若 predecessor 節(jié)點(diǎn)的右孩子不為空，同樣將指針指向 root
# 同時(shí)說明左子樹遍歷完成，置空 predecessor 右孩子，訪問 root 的右孩子
else:
# 沒有左孩子，直接訪問右孩子
if pre_node.val >= root.val and first_error == None:
first_error = pre_node
if pre_node.val >= root.val and first_error:
second_error = root
pre_node = root
# 置空 predecessor
predecessor.right = None
root = root.right
else:
# 沒有左孩子，直接訪問右孩子
if pre_node.val >= root.val and first_error == None:
first_error = pre_node
if pre_node.val >= root.val and first_error:
second_error = root
pre_node = root
root = root.right
first_error.val, second_error.val = second_error.val, first_error.val
實(shí)現(xiàn)結(jié)果
歡迎關(guān)注
公眾號 【書所集錄】
