Sự khác biệt giữa tổng các nút vị trí lẻ và nút vị trí 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 ở vị trí lẻ và vị trí chẵn. Giả sử gốc ở cấp 0, vị trí lẻ, con trái / phải của gốc ở cấp 2, con trái ở vị trí lẻ và con phải ở vị trí chẵn, v.v.

Ví dụ

    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.

Giải pháp

Sử dụng Giao dịch Đơn hàng Cấp độ. Trong quá trình duyệt, đánh dấu phần tử đầu tiên là vị trí lẻ, sau đó chuyển sang vị trí chẵn khi gặp phần tử mới, sau đó bật lại tiếp theo, v.v.

Ví dụ

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

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

Đầu ra

11