二分木の根ノード root が与えられたとき、中順走査（In-order Traversal）の結果を返す。

中順走査の順序は：左部分木 → 根ノード → 右部分木

1. 二分木ノードの定義

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

2. 再帰的実装

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverseInOrder(root, result);
        return result;
    }

    private void traverseInOrder(TreeNode node, List<Integer> output) {
        if (node == null) return;
        
        traverseInOrder(node.left, output);   // 左部分木を走査
        output.add(node.val);                 // 根ノードを記録
        traverseInOrder(node.right, output);  // 右部分木を走査
    }
}

この実装は直感的でコードが簡潔だが、木の深さが大きい場合、スタックオーバーフローのリスクがある。

3. 反復的実装（スタック使用）

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> nodeStack = new Stack<>();
        TreeNode current = root;

        while (current != null || !nodeStack.isEmpty()) {
            // 最左の葉ノードまで左に進む
            while (current != null) {
                nodeStack.push(current);
                current = current.left;
            }

            // スタックからノードをポップして値を記録
            current = nodeStack.pop();
            result.add(current.val);

            // 右部分木へ移動して繰り返す
            current = current.right;
        }

        return result;
    }
}

この方法は、再帰の内部処理を明示的にスタックで模倣する。メモリ使用量が予測可能で、深さ制限の問題を回避できるため、面接では推奨される。

なぜ再帰で毎回新しいリストを生成できないのか？

再帰呼び出しの各段階は独立したスタックフレームを持つ。もし各呼び出しで新しい List<Integer> を生成すると、子呼び出しの結果は親に伝わらない。

例：

dfs(1) → 新しいリスト A を作成 dfs(2) → 新しいリスト B を作成 → [2] を追加 dfs(null) → 戻る dfs(1) に戻り、[1] をリスト A に追加 dfs(3) → 新しいリスト C を作成 → [3] を追加

結果として、A=[1]、B=[2]、C=[3] は互いに独立し、統合できない。最終的に返されるのは最初の呼び出しのリスト A だけであるため、他の値は失われる。

int と Integer の違い

int：基本型。値そのものを保持。デフォルト値は 0。null を持てない。 Integer：int のラッパークラス。オブジェクトとして扱われる。デフォルト値は null。コレクションに格納可能。

Java のジェネリックコレクション（例：List、Map）は基本型を直接受け付けない。したがって、List<int> はコンパイルエラーになる。

ジェネリックコレクションとは？

ジェネリック（型パラメータ）は、コレクションが保持する要素の型をコンパイル時に制約する仕組みである。

List<Integer> values = new ArrayList<>(); // ✅ 正しい
// List<int> values = new ArrayList<>(); // ❌ エラー

<Integer> は「このリストは Integer のみを格納する」という意味 Java のジェネリクスは基本型（int, char, boolean など）をサポートしていない 代わりに、ラッパークラス（Integer, Character, Boolean）を使用する 型安全：取得時にキャスト不要。間違った型の挿入はコンパイル時エラー

この制約は、C++ のテンプレートと異なり、Java のジェネリクスが型消去（type erasure）に基づいているためである。

二分木のノードは存在しない場合に null で表されるため、値の型として Integer が必要になる場面が頻繁に発生する。