Pythonで二分木の通り順走査（Inorder Traversal）が回文かどうかを判定する方法

問題の概要

各ノードに0〜9のいずれかの数字が格納された二分木があるとします。この木を通り順走査（inorder traversal）した結果が回文（前から読んでも後ろから読んでも同じ並び）になっているかどうかを判定するプログラムを作成します。

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

この木の通り順走査の結果は [2, 6, 10, 6, 2] となり、左右対称の並びであるため、出力は True になります。

解決のアプローチ

この問題は、再帰を使わずにスタックを利用した反復的な通り順走査を行うことで解けます。手順は以下のとおりです。

• ルートが null の場合は True を返す
• スタック、現在ノード（curr）、結果リスト（inorder）をそれぞれ初期化する
• スタックが空でなく、かつ curr が null でない間、以下を繰り返す
  • curr が null になるまで、curr をスタックに積み、curr を左の子へ移動する
  • スタックから要素を1つ取り出し（pop）、その値を inorder の末尾に追加する
  • curr を、取り出したノードの右の子に設定する
• 最後に、inorder がその逆順リストと一致するかどうかを返す

実装例

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

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

class Solution:
   def solve(self, root):
      if not root:
         return True
      stack = []
      curr = root
      inorder = []
      while stack or curr:
         while curr:
            stack.append(curr)
            curr = curr.left
         node = stack.pop()
         inorder.append(node.val)
         curr = node.right
      return inorder == inorder[::-1]

ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

入力

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

出力

True

コードのポイント

この実装では、スタックを使って通り順走査を反復的に行っています。まず左側の子ノードをどんどんスタックに積んでいき、行き止まりに達したらスタックからノードを取り出して値を記録し、右側の子へ移動する、という流れです。これにより、深い木でも再帰によるスタックオーバーフローの心配がありません。

また、回文判定には Python のスライス inorder[::-1] を活用しています。これはリストを逆順にした新しいリストを生成する簡潔な書き方で、元のリストとの比較を1行で行えます。計算量は走査に O(n)、比較にも O(n) かかるため、全体の時間計算量は O(n)、空間計算量も O(n) となります。