जावा में एक बाइनरी ट्री की विषम स्थिति और सम स्थिति नोड्स के बीच अंतर

समस्या का विवरण

किसी दिए गए बाइनरी ट्री के साथ, विषम स्थिति और सम स्थिति पर नोड्स के योग के बीच अंतर खोजने के लिए एक प्रोग्राम लिखें। मान लें कि जड़ का स्तर 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));
   }
}