Sự khác biệt giữa tổng các nút cấp độ lẻ và cấp độ chẵn của Cây nhị phân trong Java

Tuyên bố vấn đề

Với một cây nhị phân đã cho, hãy viết một chương trình để tìm sự khác biệt giữa tổng các nút ở mức lẻ và mức chẵn. Giả sử root ở cấp 1, con trái / phải của root ở cấp 2, v.v.

Ví dụ

        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.

Giải pháp

Sử dụng Truyền tải đệ quy. Trong quá trình duyệt, trả về sự khác biệt của nút gốc và nút con bên trái và bên phải của nó.

Ví dụ

Sau đây là chương trình trong Java để tìm đầu ra cần thiết.

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

Đầu ra

-9