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

समस्या कथन

एक दिए गए बाइनरी ट्री के साथ, विषम स्थिति पर नोड्स के योग और सम स्थिति पर नोड्स के योग के बीच अंतर ज्ञात करने के लिए एक प्रोग्राम लिखें। रूट को लेवल 0, विषम स्थिति मानें, रूट के बाएं/दाएं चाइल्ड को लेवल 2, बाएं चाइल्ड को विषम स्थिति और दाएं चाइल्ड को सम स्थिति मानें और इसी तरह आगे।

उदाहरण

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

विषम स्थितियों पर नोड्स का योग = 5 + 2 + (1 + 8) + (3 + 9) = 5 + 2 + 9 + 12 = 28
सम स्थितियों पर नोड्स का योग = 0 + 6 + 4 + 7 = 17
अंतर = 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 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 queue = new LinkedList(); 
        queue.add(tree); 
        System.out.println(difference(queue)); 
    } 
}