ความแตกต่างระหว่างผลรวมของโหนดระดับคี่และโหนดระดับคู่ของไบนารีทรีใน Java

คำชี้แจงปัญหา

ด้วยไบนารีทรีที่กำหนด ให้เขียนโปรแกรมเพื่อค้นหาความแตกต่างระหว่างผลรวมของโหนดที่ระดับคี่และระดับคู่ สมมติว่า root ที่ระดับ 1 ลูกซ้าย/ขวาของ root ที่ระดับ 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.

วิธีแก้ปัญหา

ใช้ Traversal แบบเรียกซ้ำ ในระหว่างการข้ามผ่าน ให้คืนค่าส่วนต่างของโหนดรูทและชายด์ด้านซ้ายและขวา

ตัวอย่าง

ต่อไปนี้เป็นโปรแกรมใน Java เพื่อค้นหาผลลัพธ์ที่ต้องการ

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