Pythonで二分木の最大深度を求める方法｜再帰を使った実装例を解説

Pythonで二分木の最大深度を求める

二分木が与えられたとき、その最大深度を求める問題を考えます。木の最大深度とは、根（ルート）から葉ノードまでの最も長い経路をたどったときに通過するノード数のことです。

例えば、下図のような二分木の場合、最大深度は 3 となります。

解法のアプローチ

この問題は再帰を使うことで、非常にシンプルに解くことができます。手順は以下のとおりです。

• 再帰用のヘルパーメソッド solve(root, depth=0) を定義します。
• root が空（None）の場合は、そこまでの深さ depth をそのまま返します。
• それ以外の場合は、左部分木に対する solve(left, depth+1) と右部分木に対する solve(right, depth+1) のうち、大きい方の値を返します。

各ノードを一段深く潜るごとに depth を1ずつ増やしていき、葉に到達した時点での深さを返すことで、自動的に最長経路の長さが求まります。

実装例

以下にPythonでの実装例を示します。

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

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.solve(root)

    def solve(self, root, depth=0):
        if root == None:
            return depth
        return max(self.solve(root.left, depth+1),
                   self.solve(root.right, depth+1))

tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
print(ob1.maxDepth(tree1))

入力

tree1 = make_tree([1,2,2,3,4,None,3])

出力

3

コードの解説

• TreeNodeクラス：各ノードはデータ（data）、左の子（left）、右の子（right）を持ちます。
• insert関数・make_tree関数：リスト形式のデータから幅優先（BFS）の要領で二分木を構築する補助関数です。None が渡された場合はダミーノードを挿入します。
• maxDepthメソッド：外部からのエントリーポイントであり、内部で solve を呼び出します。
• solveメソッド：再帰の本体です。ノードが存在しない地点に到達したときの depth を返し、左右の結果の最大値を上位に伝播させることで、木全体の最大深度が得られます。

計算量について

• 時間計算量：O(n) ― 各ノードをちょうど1回ずつ訪問するため、ノード数 n に比例した処理時間となります。
• 空間計算量：O(h) ― 再帰呼び出しのスタックの深さは木の高さ h に依存します。木が片側に偏っている最悪ケースでは O(n) になります。