समस्या का विवरण
किसी दिए गए बाइनरी ट्री के साथ, विषम स्तर और सम स्तर पर नोड्स के योग के बीच अंतर खोजने के लिए एक प्रोग्राम लिखें। स्तर 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.
समाधान
रिकर्सिव ट्रैवर्सल का प्रयोग करें। ट्रैवर्सल के दौरान, रूट नोड और उसके बाएँ और दाएँ बच्चे का अंतर लौटाएँ।
उदाहरण
आवश्यक आउटपुट खोजने के लिए जावा में प्रोग्राम निम्नलिखित है।
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