二分木走査パターン

基本

カテゴリ: trees

概要

二分木走査は、二分木のすべてのノードを特定の順序で訪問するプロセスです。主な走査方法には、前順（Pre-order）、中順（In-order）、後順（Post-order）、レベル順（Level-order）の4種類があります。これらの走査方法は、木構造のデータを処理する際の基本的なアルゴリズムであり、多くの木関連の問題を解決するための基礎となります。

コードテンプレート

Java

Python

- 再帰的実装
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

// 前順走査（Pre-order）
public void preorder(TreeNode root) {
    if (root == null) return;
    
    // ルートを処理
    System.out.print(root.val + " ");
    // 左部分木を走査
    preorder(root.left);
    // 右部分木を走査
    preorder(root.right);
}

// 中順走査（In-order）
public void inorder(TreeNode root) {
    if (root == null) return;
    
    // 左部分木を走査
    inorder(root.left);
    // ルートを処理
    System.out.print(root.val + " ");
    // 右部分木を走査
    inorder(root.right);
}

// 後順走査（Post-order）
public void postorder(TreeNode root) {
    if (root == null) return;
    
    // 左部分木を走査
    postorder(root.left);
    // 右部分木を走査
    postorder(root.right);
    // ルートを処理
    System.out.print(root.val + " ");
}

// レベル順走査（Level-order）
public void levelOrder(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        
        if (node.left != null) {
            queue.offer(node.left);
        }
        
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

二分木走査前順中順後順レベル順Pre-orderIn-orderPost-orderLevel-orderDFSBFSツリートラバーサル

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
二分木の最大深さ（Maximum Depth of Binary Tree）: 木の最大深さを求める
2
対称的な木（Symmetric Tree）: 木が左右対称かどうかを判定する
3
二分木の反転（Invert Binary Tree）: 二分木を左右反転する
4
二分木のパス合計（Path Sum）: 特定の合計値を持つパスが存在するかを判定する
5
二分探索木の検証（Validate Binary Search Tree）: 木がBSTの条件を満たすかを検証する

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

易

二分木の最大深さ

二分木の根ノードが与えられたとき、その木の最大深さを求めてください。二分木の最大深さとは、根ノードから最も遠い葉ノードまでの最長パスに沿ったノードの数です。 **注意**: 葉ノードとは、子を持...

易

二分木の中順走査

二分木の根ノードが与えられたとき、その木の中順走査（inorder traversal）の結果を返してください。中順走査とは、左の子 → 自分自身 → 右の子の順に訪問する走査方法です。...

易

二分木の前順走査

二分木の根ノードが与えられたとき、その木の前順走査（preorder traversal）の結果を返してください。前順走査とは、自分自身 → 左の子 → 右の子の順に訪問する走査方法です。...