【Java】二分木における奇数レベルと偶数レベルのノード合計値の差を求める方法

問題の概要

与えられた二分木（バイナリツリー）に対して、奇数レベルにあるノードの合計値と偶数レベルにあるノードの合計値の差を求めるプログラムを作成します。

ここで、ルートノードをレベル1とし、その左・右の子ノードをレベル2、さらにその下をレベル3…というようにレベルを定義します。

具体例

以下のような二分木を考えてみましょう。

        5
      /   \
     2     6
    / \     \
   1   4     8
  /    / \
 3    7   9

この木に対して各レベルの合計を計算すると、次のようになります。

• 奇数レベル（レベル1・3）の合計： 5 + 1 + 4 + 8 = 18
• 偶数レベル（レベル2）の合計： 2 + 6 + 3 + 7 + 9 = 27

したがって、差は「18 − 27 = -9」となります。

解法のアプローチ

この問題は再帰的な走査（Recursive Traversal）を使うことで、非常にシンプルに解くことができます。

ポイントは次の通りです。

• あるノードの値から、その左部分木と右部分木で計算された差を引いて返す
• この操作を再帰的に繰り返すことで、結果的に「奇数レベルの合計 − 偶数レベルの合計」が自動的に求まる

これは、隣接するレベル同士の符号が交互に入れ替わる性質を利用したエレガントな手法です。ルート（レベル1）は正の符号、レベル2は負の符号、レベル3は再び正の符号…というように、深さごとに符号が反転していくためです。

Javaでの実装例

以下が実際のJavaプログラムです。

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        this.left = this.right = null;
    }
}

public class JavaTester {

    // サンプルツリーを構築するメソッド
    public static Node getTree() {
        Node root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(4);
        root.left.right.left = new Node(3);
        root.right.right = new Node(8);
        root.right.right.right = new Node(9);
        root.right.right.left = new Node(7);
        return root;
    }

    // 奇数レベルと偶数レベルの合計差を再帰的に計算するメソッド
    public static int difference(Node node) {
        if (node == null) return 0;
        return node.data - difference(node.left) - difference(node.right);
    }

    public static void main(String args[]) {
        Node tree = getTree();
        System.out.println(difference(tree));
    }
}

コードの解説

Nodeクラス

二分木の各ノードを表すクラスです。整数値 data と、左右の子ノードへの参照 left・right を持ちます。

differenceメソッド

この問題の核心となるメソッドです。処理の流れは以下の通りです。

1. ノードが null の場合は 0 を返す（ベースケース）
2. それ以外の場合は、「現在のノードの値 − 左部分木の差 − 右部分木の差」を返す

一見シンプルですが、再帰呼び出しが深くなるにつれて符号が交互に反転するため、結果として奇数レベルの合計から偶数レベルの合計を引いた値が得られます。

実行結果

-9

想定どおり、奇数レベルの合計（18）と偶数レベルの合計（27）の差である -9 が出力されました。

計算量について

• 時間計算量： O(n) — 各ノードを一度だけ訪問するため
• 空間計算量： O(h) — 再帰のスタックの深さは木の高さ h に依存（最悪の場合 O(n)）

まとめ

二分木の奇数レベルと偶数レベルのノード合計の差は、再帰を使ったシンプルな実装で効率よく求められます。「自分の値から子の結果を引く」というたった一行の再帰式が、レベルごとの符号反転を自然に表現できるのがこのアルゴリズムの美しいところです。二分木の再帰処理の理解を深める良い練習問題として、ぜひ参考にしてください。