Pythonで二分探索木のノードの兄弟の値を見つけるプログラム

問題概要

値 k と二分探索木が与えられます。この木では、各ノードは葉ノードであるか、必ず2つの子を持っています。値 k を持つノードを見つけ、その兄弟ノードの値を返す必要があります。

例えば、次のような二分探索木が与えられたとします。

k = 4 の場合、出力は 10 になります(4の兄弟ノードが10だからです)。

解法のアプローチ

この問題は、二分探索木の性質(左の子 < 親 < 右の子)を利用することで効率的に解けます。手順は以下の通りです。

1. 関数 util() を定義します。引数として root(現在のノード)、k(探す値)、ans(結果を格納するリスト)を受け取ります。
2. 現在のノードが葉ノード(左右どちらの子も存在しない)の場合、処理を終了して戻ります。
3. k が現在のノードの値より大きい場合:
   • 右の子の値が k と一致するなら、左の子の値を ans に追加して戻ります。
   • 一致しなければ、右の子に対して util() を再帰的に呼び出します。
4. k が現在のノードの値より小さい場合:
   • 左の子の値が k と一致するなら、右の子の値を ans に追加して戻ります。
   • 一致しなければ、左の子に対して util() を再帰的に呼び出します。
5. メインの処理では以下を行います。
   • ans を空のリストとして初期化します。
   • util(root, k, ans) を呼び出します。
   • ans[0] を返します。

それでは、実際の実装を見て理解を深めましょう。

実装例(Python)

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right


def util(root, k, ans):
    # 葉ノードに到達したら終了
    if root.left is None and root.right is None:
        return
    if k > root.val:
        if root.right.val == k:
            # 兄弟ノード(左の子)の値を記録
            ans.append(root.left.val)
            return
        else:
            util(root.right, k, ans)
    if k < root.val:
        if root.left.val == k:
            # 兄弟ノード(右の子)の値を記録
            ans.append(root.right.val)
            return
        else:
            util(root.left, k, ans)


class Solution:
    def solve(self, root, k):
        ans = []
        util(root, k, ans)
        return ans[0]


root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)

ob1 = Solution()
print(ob1.solve(root, 4))

入力

root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
k = 4

出力

10

まとめ

このアルゴリズムは、二分探索木の性質を活かして目的のノードまで効率的にたどり着きます。各ステップで k と現在のノードの値を比較し、子ノードのどちらかが k と一致した時点で、もう一方の子(兄弟)の値を記録します。計算量は木の高さに比例する O(h) となり、バランスの取れた二分探索木であれば非常に高速に動作します。