জাভাতে একটি বাইনারি ট্রির বিজোড় অবস্থান এবং জোড় অবস্থানের নোডের যোগফলের মধ্যে পার্থক্য

সমস্যা বিবৃতি

একটি প্রদত্ত বাইনারি ট্রি দিয়ে, বিজোড় অবস্থান এবং জোড় অবস্থানে নোডের যোগফলের মধ্যে পার্থক্য খুঁজে বের করার জন্য একটি প্রোগ্রাম লিখুন। 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.

সমাধান

লেভেল অর্ডার ট্রাভার্সাল ব্যবহার করুন। ট্র্যাভার্সালের সময়, প্রথম উপাদানটিকে বিজোড় অবস্থান হিসাবে চিহ্নিত করুন এবং তারপরে নতুন উপাদানের মুখোমুখি হওয়ার পরেও স্যুইচ করুন এবং তারপরে পরবর্তীতে আবার চালু করুন।

উদাহরণ

প্রয়োজনীয় আউটপুট খুঁজে পেতে জাভাতে প্রোগ্রামটি নিম্নরূপ।

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));
   }
}