Javaで二分木の奇数位置ノードと偶数位置ノードの合計差を求める方法

問題の概要

与えられた二分木に対して、「奇数位置にあるノードの合計」と「偶数位置にあるノードの合計」の差を求めるプログラムを作成します。

位置の定義は以下のとおりです。ルートをレベル0とし、各レベル内で先頭のノードを「奇数位置」、次のノードを「偶数位置」として交互に判定していきます。つまり、ルートは奇数位置、その子ノードたちは左から順に偶数位置・奇数位置・偶数位置…というように、レベルごとに交互に振り分けられます。

具体例

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

この木の場合、各ノードの位置は次のように分類されます。

• レベル0：5（奇数）
• レベル1：2（奇数）、6（偶数）
• レベル2：1（奇数）、4（偶数）、8（奇数）
• レベル3：3（奇数）、7（偶数）、9（奇数）

奇数位置ノードの合計
= 5 + 2 + (1 + 8) + (3 + 9)
= 28

偶数位置ノードの合計
= 6 + 4 + 7
= 17

差 = 28 - 17 = 11

解法のアプローチ

この問題はレベル順走査（幅優先探索：BFS）を使うことで効率的に解けます。

キュー（LinkedList）を利用して木をレベルごとに処理し、各レベル内でノードを順番に取り出しながら、フラグ（isOdd）を交互に切り替えることで奇数位置・偶数位置を判定します。具体的には、レベルの最初のノードを奇数位置として合計に加算し、次のノードからは偶数位置として加算、また次は奇数位置…という処理を繰り返します。

計算量は、すべてのノードを一度ずつ訪問するため O(n)、キューに必要な領域は最大で木の幅分となるため空間計算量も O(n) です。

Javaでの実装例

以下は、上記のアプローチを実装したJavaプログラムです。

import java.util.LinkedList;

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(LinkedList<Node> queue){
      if(queue.isEmpty()) return 0;
      int evenSum = 0;
      int oddSum = 0;

      while(true){
         int nodes = queue.size();
         if(nodes == 0) break;
         boolean isOdd = true;
         while(nodes > 0){
            Node node = queue.peek();
            if(isOdd) oddSum += node.data;
            else evenSum += node.data;
            queue.remove();
            nodes--;
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
            isOdd = !isOdd;
         }
      }
      return oddSum - evenSum;
   }

   public static void main(String args[]){
      Node tree = getTree();
      LinkedList<Node> queue = new LinkedList<Node>();
      queue.add(tree);
      System.out.println(difference(queue));
   }
}

コードのポイント

• getTree()メソッド：例で示した二分木を構築して返します。
• difference()メソッド：キューを使ったレベル順走査を行い、外側のwhileループでレベルを、内側のwhileループでそのレベルのノードを処理します。
• isOddフラグ：ノードを1つ処理するごとに反転させることで、同じレベル内でも奇数位置と偶数位置を交互に判定できます。

実行結果

11

プログラムを実行すると、奇数位置ノードの合計（28）と偶数位置ノードの合計（17）の差である「11」が出力されます。