Recover Binary Search Tree

アルゴリズム概要

問題

二分探索木（BST）において、ちょうど2つのノードの値が誤って入れ替わっている。 木の構造を変更せずに、値のスワップのみでBSTを修復する。

入出力例

入力: root = [3,1,4,null,null,2]  (3と2が入れ替わっている)
出力: [2,1,4,null,null,3]

      3*              2
     / \    →       / \
    1   4          1   4
       /              /
      2*             3

戦略

• 中順走査でBSTを走査すると昇順列が得られる
• 2ノード入れ替えにより、昇順列に1〜2箇所の違反（prev > curr）が発生
• 違反箇所から入れ替わったノードを特定し、値をスワップして修復

違反パターン

ステップバイステップ解説

Python実装

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        BST修復（再帰版）
        Time: O(n), Space: O(h)
        """
        self.first = self.second = self.prev = None
        self._inorder(root)
        # 値のスワップ
        self.first.val, self.second.val = self.second.val, self.first.val

    def _inorder(self, node: Optional[TreeNode]) -> None:
        if not node:
            return

        # 左部分木を走査
        self._inorder(node.left)

        # 違反チェック: prev > curr はBST違反
        if self.prev and self.prev.val > node.val:
            if not self.first:
                self.first = self.prev  # 最初の違反
            self.second = node  # 常に更新

        self.prev = node

        # 右部分木を走査
        self._inorder(node.right)

フローチャート

フローの説明：

1初期化: first, second, prev を None に設定

2ノードがNoneなら即座にreturn（基底条件）

3左部分木を再帰的に走査（中順走査の「左」）

4違反チェック: prev.val > node.val ならBST違反

5最初の違反で first = prev を設定

6常に second = node を更新（隣接/非隣接両対応）

7prev を現在のノードに更新

8右部分木を再帰的に走査（中順走査の「右」）

9全走査完了後、first と second の値をスワップして修復完了

計算量分析

詳細分析

• 時間 O(n): 全ノードを1回走査（Morris版は最大2回）
• 空間 O(h): 再帰コールスタックの深さ（hは木の高さ）
• 空間 O(1): Morris版はスレッディングで追加メモリ不要
• スワップ: 最後に1回の値交換のみ（O(1)）