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