Pythonで二分木の2番目に深い葉ノードの深さを求めるプログラム

問題の概要

二分木が与えられたとき、2番目に深い葉ノードの深さを求めることを考えます。最も深い葉が複数存在する場合は、その次に高い位置にある葉ノードが「2番目に深い葉」とみなされます。なお、根（ルート）の深さは0であるとします。

入力例と出力

例えば、次のような二分木が与えられた場合を考えてみましょう。

この木では、最も深い葉はノード7とノード8（深さ3）であり、その次に深い葉はノード3（深さ1）です。したがって、出力は 1 となります。

解法のアプローチ

この問題は、木をレベル（深さ）ごとに順番に辿っていく幅優先探索（BFS）の考え方を使うと、シンプルに解くことができます。各レベルで最初に見つかった葉ノードの深さを記録していき、直前に記録した値を保持しておくことで、最終的に「2番目に深い葉」の深さが求まります。

アルゴリズムの手順

• 根がnullの場合は、nullを返します。
• 新しいリストnodesを作成し、その末尾に根を挿入します。
• count := 0、prev := 0、now := 0 と初期化します。
• nodesが空でない間、以下の処理を繰り返します。
  • 新しいリストnewを作成し、flag := True とします。
  • nodes内の各ノードに対して、以下を判定します。
    • flagがTrueで、かつノードの左の子・右の子がどちらもnull（＝葉ノード）の場合：prev := now、now := count と更新し、flagをFalseにします。
    • 左の子が存在する場合は、newの末尾に追加します。
    • 右の子が存在する場合は、newの末尾に追加します。
  • nodes := new として次のレベルへ進み、count を1増やします。
• ループ終了後、prevを返します。

ここで、nowには「最後に葉が見つかったレベル（＝最深部）」の深さが入り、prevには「その一つ前のレベルで最初に見つかった葉」の深さが入ります。この仕組みにより、prevが2番目に深い葉の深さを表すことになります。

Pythonでの実装例

それでは、上記のアルゴリズムを実際にPythonで実装してみましょう。

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

class Solution:
    def solve(self, root):
        if root is None:
            return None
        nodes = []
        nodes.append(root)
        count = 0
        prev = 0
        now = 0
        while nodes:
            new = []
            flag = True
            for node in nodes:
                if flag and (not node.left) and (not node.right):
                    prev = now
                    now = count
                    flag = False
                if node.left:
                    new.append(node.left)
                if node.right:
                    new.append(node.right)
            nodes = new
            count += 1
        return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

入力

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)

出力

1

まとめ

本記事では、二分木から2番目に深い葉ノードの深さを求める方法を紹介しました。レベルごとにノードを辿るBFSの考え方を応用することで、木を一度走査するだけで目的の値を取得できます。計算量はノード数をNとするとO(N)、空間計算量も最大でO(N)となり、非常に効率的な解法です。同様の手法は、木の最大深度やレベルごとのノード集合を求める問題にも応用できるので、ぜひ覚えておきましょう。