Pythonで二分木の左端の最深ノードを求めるプログラム

二分木が与えられたとき、最も深い位置にあるノードの値を求めることを考えます。最深ノードが複数存在する場合は、その中で最も左側にあるノードの値を返します。

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

この場合、出力は 4 になります。最も深いレベルには 4 と 7 の2つのノードがありますが、4 の方が左側に位置しているためです。

解法のアプローチ

この問題は、幅優先探索（BFS）を使って木をレベルごとに走査することで効率的に解けます。各レベルの最初のノード（＝そのレベルの最も左のノード）の値を記録していき、すべてのレベルの走査が完了した時点で記録されている値が、最も深いレベルの左端ノードの値になります。

具体的な手順は以下の通りです。

• ルートノードのみを含むキューを用意します。
• 変数 left_max の初期値として、ルートの値を設定します。
• キューが空になるまで、以下の処理を繰り返します。
  • 現在のキューのサイズを level_size として取得します（これは現在のレベルのノード数に相当します）。
  • i を 0 から level_size - 1 まで繰り返します。
    • キューの先頭からノードを取り出し、temp とします。
    • i が 0 のとき（＝レベルの最初のノードのとき）、left_max に temp の値を代入します。
    • temp の左の子が存在すれば、キューの末尾に追加します。
    • temp の右の子が存在すれば、キューの末尾に追加します。
• ループが終了したら、left_max を返します。

それでは、実際の実装例を見てみましょう。

実装例

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

class Solution:
   def solve(self, root):
      queue = [root]
      left_max = root.val
      while len(queue) > 0:
         level_size = len(queue)
         for i in range(level_size):
            temp = queue.pop(0)
            if i == 0:
               left_max = temp.val
            if temp.left:
               queue.append(temp.left)
            if temp.right:
               queue.append(temp.right)
      return left_max

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

入力

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

出力

4

計算量の分析

時間計算量： O(n) ― 木に含まれる各ノードを一度ずつ訪問するためです。
空間計算量： O(w) ― w は木の最大幅であり、キューに同時に格納されるノード数の最大値に依存します。

このように、BFSによるレベル順走査を利用すれば、最深ノードの左端の値をシンプルかつ効率的に求めることができます。