Java에서 이진 트리의 홀수 위치 노드와 짝수 위치 노드 합계의 차이점

<시간/>

문제 설명

주어진 이진 트리를 사용하여 홀수 위치와 짝수 위치에 있는 노드의 합 사이의 차이를 찾는 프로그램을 작성하십시오. 레벨 0에서 루트, 홀수 위치, 레벨 2에서 루트의 왼쪽/오른쪽 자식, 홀수 위치에서 왼쪽 자식, 짝수 위치에서 오른쪽 자식 등으로 가정합니다.

예

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

Sum of nodes at odd positions
= 5 + 2 + (1 + 8) + (3 + 9)
= 5 + 2 + 9 + 12
= 28
Sum of nodes at even level
= 0 + 6 + 4 + 7
= 17
Difference = 11.

해결책

레벨 순서 순회를 사용합니다. 순회하는 동안 첫 번째 요소를 홀수 위치로 표시한 다음 새 요소가 발견되면 짝수로 전환한 다음 다음으로 다시 전환하는 식으로 진행합니다.

예

다음은 필요한 출력을 찾는 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));
   }
}