Chênh lệch tổng nút vị trí lẻ và chẵn của cây nhị phân trong Java

Đề bài

Cho một cây nhị phân, viết chương trình tìm chênh lệch 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à cứ thế tiếp tục.

Ví dụ

    5 
   / \ 
  2   6 
 / \   \ 
1   4   8 
/   / \ 
3   7   9 
Tổng nút vị trí lẻ = 5 + 2 + (1 + 8) + (3 + 9) = 5 + 2 + 9 + 12 = 28 
Tổng nút vị trí chẵn = 0 + 6 + 4 + 7 = 17 
Chênh lệch = 11.

Giải pháp

Sử dụng Duyệt theo cấp độ (Level Order Traversal). Trong quá trình duyệt, đánh dấu phần tử đầu tiên là vị trí lẻ sau đó chuyển sang chẵn khi gặp phần tử mới và quay lại lẻ ở phần tử tiếp theo, v.v.

Ví dụ

Chương trình Java sau tìm kết quả yêu cầu.

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

Kết quả

11