DFS分析

深さ優先探索(DFS)は子ノードを先に訪問し、その後親ノードを訪問する手法です。訪問順序により以下の3種類に分類されます：

• 前順序(pre-order)：根→左→右
• 中順序(in-order)：左→根→右
• 後順序(post-order)：左→右→根

DFS非再帰実装

前順序と後順序

前順序と後順序の実装は類似したロジックで実現できます。前順序訪問は根ノードから開始し、左部分木、右部分木の順で訪問します。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    if (root == null) return results;
    Deque<TreeNode> nodeStack = new ArrayDeque<>();
    nodeStack.push(root);
    
    while (!nodeStack.isEmpty()) {
        TreeNode current = nodeStack.pop();
        results.add(current.val);
        if (current.right != null) nodeStack.push(current.right);
        if (current.left != null) nodeStack.push(current.left);
    }
    return results;
}

後順序訪問は前順序訪問の変形として実装可能です。訪問順序を「根→右→左」とし、結果を反転することで「左→右→根」の順序を得ます。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    if (root == null) return results;
    Deque<TreeNode> nodeStack = new ArrayDeque<>();
    nodeStack.push(root);
    
    while (!nodeStack.isEmpty()) {
        TreeNode current = nodeStack.pop();
        results.add(current.val);
        if (current.left != null) nodeStack.push(current.left);
        if (current.right != null) nodeStack.push(current.right);
    }
    Collections.reverse(results);
    return results;
}

中順序

中順序訪問では異なるアプローチが必要です：

1. 左部分木を最深部まで探索しノードをスタックに追加
2. スタックからノードを取り出し結果に追加
3. 右部分木に対して同様の処理を適用

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    Deque<TreeNode> nodeStack = new ArrayDeque<>();
    TreeNode current = root;
    
    while (current != null || !nodeStack.isEmpty()) {
        while (current != null) {
            nodeStack.push(current);
            current = current.left;
        }
        current = nodeStack.pop();
        results.add(current.val);
        current = current.right;
    }
    return results;
}