二分木を扱う際に必須となる「先行順」「中間順」「後行順」の三巡回について、再帰と反復（スタック利用）の両アプローチで実装を整理する。

先行順巡回（Pre-order Traversal）

ノード → 左部分木 → 右部分木の順で値を収集する。

再帰実装（Python）

from typing import Optional, List

class TreeNode:
    def __init__(self, val: int = 0,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def preorder(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        left_vals = self.preorder(root.left)
        right_vals = self.preorder(root.right)
        return [root.val, *left_vals, *right_vals]

反復実装（Java）

import java.util.*;

class Solution {
    public List<Integer> preorderIt(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        if (root != null) st.push(root);

        while (!st.isEmpty()) {
            TreeNode cur = st.pop();
            if (cur != null) {
                // 右 → 左 → 中 の逆順に積む
                if (cur.right != null) st.push(cur.right);
                if (cur.left  != null) st.push(cur.left);
                st.push(cur);
                st.push(null); // 処理済み印
            } else {
                out.add(st.pop().val);
            }
        }
        return out;
    }
}

中間順巡回（In-order Traversal）

左部分木 → ノード → 右部分木の順で値を収集する。

再帰実装（Python）

class Solution:
    def inorder(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        return [*self.inorder(root.left),
                root.val,
                *self.inorder(root.right)]

反復実装（Java）

public List<Integer> inorderIt(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        // 最左端まで潜る
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.add(curr.val);
        curr = curr.right;
    }
    return res;
}

後行順巡回（Post-order Traversal）

左部分木 → 右部分木 → ノードの順で値を収集する。

再帰実装（Python）

class Solution:
    def postorder(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        return [*self.postorder(root.left),
                *self.postorder(root.right),
                root.val]

反復実装（Java）

public List<Integer> postorderIt(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) return res;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val); // 逆順に追加
        if (node.left  != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}

実装の選択指針

• 再帰：コードが短く直感的。木の高さが深くない場合に最適。
• 反復（スタック）：スタックオーバーフローを回避できる。深い木や制限厳しい環境で有効。
• Deque を使った反復：ポインタを左右に振ることで、より自然な順序でノードを処理できる。

三巡回の違いは「いつ値を記録するか」のタイミングのみであり、再帰・反復のどちらを選ぶかは制約と可読性のバランスで決めるとよい。