【Python】二分木の後順走査（ポストオーダートラバーサル）を再帰なしで実装する方法

二分木の後順走査（ポストオーダートラバーサル）とは？

二分木の後順走査（ポストオーダートラバーサル）は、「左の子 → 右の子 → 親ノード」の順ですべてのノードを訪問する探索手法です。再帰を使えば簡潔に書けますが、本記事では再帰を使わない反復処理（イテレーティブ）による実装方法を詳しく解説します。

例として、次のような二分木を考えてみましょう。

この木を後順走査すると、出力は次のようになります。

[9, 15, 7, 10, -10]

後順走査は、木のメモリ解放や数式表現木の評価など、「子ノードを先に処理してから親を処理したい」という場面で活躍する、基本的かつ重要なアルゴリズムです。

反復処理による解法の手順

再帰呼び出しの代わりにスタックを使用します。各ノードに対して「未訪問（0）／訪問済み（1）」を示す状態フラグを持つペアを管理するのがポイントです。手順は以下の通りです。

1. rootがNoneの場合は、空の配列を返す
2. 結果を格納する配列 res を作成する
3. スタックを定義し、ペア [root, 0] をプッシュする
4. スタックが空になるまで以下を繰り返す
   • スタックの先頭要素 node を取り出す（pop）
   • node の状態フラグが 0 の場合
     • current := node の第1要素（ノード本体）
     • (current, 1) をスタックに挿入する
     • current の右の子が存在すれば [右の子, 0] をプッシュする
     • current の左の子が存在すれば [左の子, 0] をプッシュする
   • 状態フラグが 1 の場合は、そのノードの値を res に追加する
5. res を返す

ここで「右の子を先に、左の子を後にプッシュする」点が重要です。スタックは後入れ先出し（LIFO）のため、左の子が先に取り出され、結果として「左 → 右 → 親」という後順の順序が自然に実現されます。

Pythonでの実装例

以下が実際の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 postorderTraversal(self, root):
        if not root:
            return []
        res = []
        stack = [[root, 0]]
        while stack:
            node = stack[-1]
            stack.pop()
            if node[1] == 0:
                current = node[0]
                stack.append([current, 1])
                if current.right:
                    stack.append([current.right, 0])
                if current.left:
                    stack.append([current.left, 0])
            else:
                if node[0].data != 0:
                    res.append(node[0].data)
        return res

ob = Solution()
root = make_tree([-10, 9, 10, None, None, 15, 7])
print(ob.postorderTraversal(root))

コードの構成

• TreeNodeクラス: 木の各ノードを表します。値（data）と左右の子（left / right）を持ちます。
• insert関数・make_tree関数: 配列の要素を幅優先で木に挿入し、二分木を構築するためのヘルパーです。Noneは欠損ノードを表します。
• Solution.postorderTraversal: 本題となる後順走査の本体です。スタックと状態フラグにより、再帰なしで反復処理を実現しています。

実行結果

入力

[-10, 9, 10, None, None, 15, 7]

出力

[9, 15, 7, 10, -10]

計算量

• 時間計算量: O(n) ― 各ノードは最大2回スタックに出入りします。
• 空間計算量: O(n) ― 木が片側に偏っている場合、スタックに最大n個の要素が積まれる可能性があります。

まとめ

スタックに「ノードと状態フラグのペア」を積むことで、再帰なしでもエレガントに後順走査を実装できます。このテクニックは前順・中順走査の反復版にも応用可能なので、あわせて習得しておくとよいでしょう。