Javaのバイナリツリーの奇数レベルノードと偶数レベルノードの合計の違い

問題の説明

与えられた二分木で、奇数レベルと偶数レベルのノードの合計の違いを見つけるプログラムを作成します。レベル1でルートを想定し、レベル2でルートの左/右の子などを想定します。

例

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

Sum of nodes at odd level
= 5 + 1 + 4 + 8
= 18
Sum of nodes at even level
= 2 + 6 + 3 + 7 + 9
= 27
Difference = -9.

解決策

再帰的走査を使用します。トラバーサル中に、ルートノードとその左右の子の差を返します。

例

以下は、必要な出力を見つけるための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));
   }
}

出力

-9