二分木の直径を求める方法

以下に、二分木の直径を求めるためのシンプルで簡単なアルゴリズムといくつかのコード例を示します。

アルゴリズムの手順:

1. 二分木の各ノードに対して、そのノードを根とする部分木の高さを求めます。
2. 二分木の各ノードに対して、そのノードを通過する最長パスの長さを求めます。これは、そのノードの左部分木の高さと右部分木の高さの合計になります。
3. 各ノードの最長パスの長さを比較し、最大値を直径とします。

以下に、Pythonでのコーディング例を示します。

# 二分木のノードを表すクラス
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
# 二分木の直径を求める関数
def diameter_of_binary_tree(root):
    # ヘルパー関数: あるノードを根とする部分木の高さを求める
    def height(node):
        if node is None:
            return 0
        left_height = height(node.left)
        right_height = height(node.right)
        return 1 + max(left_height, right_height)
    # ヘルパー関数: あるノードを根とする部分木を通過する最長パスの長さを求める
    def longest_path(node):
        if node is None:
            return 0
        left_path = height(node.left)
        right_path = height(node.right)
        return left_path + right_path
    if root is None:
        return 0
    # 各ノードの最長パスの長さを比較し、最大値を直径とする
    left_diameter = diameter_of_binary_tree(root.left)
    right_diameter = diameter_of_binary_tree(root.right)
    curr_diameter = longest_path(root)
    return max(left_diameter, right_diameter, curr_diameter)
# 二分木の例を作成
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
# 二分木の直径を求める
diameter = diameter_of_binary_tree(root)
print("二分木の直径:", diameter)

このコードでは、Nodeクラスを使用して二分木のノードを表し、diameter_of_binary_tree関数で直径を求めています。与えられた二分木の直径を計算し、結果を表示しています。

以上が、二分木の直径を求めるためのシンプルで簡単な方法とコード例です。このアルゴリズムとコードを使用すると、与えられた二分木の直径を効率的に求めることができます。