Pythonで二分木の後順走査（ポストオーダートラバーサル）を反復処理で実装する方法

二分木が与えられたとき、再帰を使わずに反復処理（イテレーティブな手法）で後順走査（ポストオーダートラバーサル）の結果を求める問題を考えてみましょう。

たとえば、次のような二分木があるとします。

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

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

後順走査とは

後順走査は、各ノードを「左の子孫 → 右の子孫 → 自分自身」の順に訪問する走査方法です。上記の例では、まず左部分木の 9 を訪問し、次に右部分木の 15、7、その親の 10、最後に根の -10 を訪問します。

解法のアプローチ

再帰を使わずに後順走査を実現するには、スタックと「訪問済みフラグ」を組み合わせるのが有効です。各ノードを [ノード, フラグ] のペアとして管理し、フラグが 0 の場合はまだ処理前、1 の場合は子ノードの処理が完了して値を出力できる状態を表します。

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

• 根が null の場合は空の配列を返します。

• 結果を格納する配列 res を作成します。

• スタックを定義し、[root, 0] のペアをプッシュします。

• スタックが空になるまで、以下を繰り返します。

  • スタックの先頭要素を取り出します。

  • ペアの2番目の値（フラグ）が 0 の場合：

    • 1番目の値を current とします。

    • (current, 1) をスタックにプッシュします。

    • current に右の子が存在すれば、[右の子, 0] をプッシュします。

    • current に左の子が存在すれば、[左の子, 0] をプッシュします。

  • フラグが 0 以外の場合：ノードの値を res に追加します。

• 最後に res を返します。

ポイントは、右の子を先に、左の子を後にプッシュすることです。スタックはLIFO（後入れ先出し）なので、これにより左の子が先に処理され、正しい走査順序が保たれます。

実装例

以下に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))

入力

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

出力

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

計算量について

この手法では、各ノードを最大2回スタックにプッシュするため、時間計算量は O(n)、空間計算量もスタックの使用により O(n) となります。再帰呼び出しによるスタックオーバーフローのリスクがないため、深い木を扱う場合にも安全に動作するのが利点です。