ความแตกต่างระหว่างผลรวมโหนดตำแหน่งคี่และคู่ของ Binary Tree ใน Java

โจทย์

ได้รับ Binary Tree ให้เขียนโปรแกรมหาความต่างระหว่างผลรวมโหนดที่ตำแหน่งคี่และตำแหน่งคู่ สมมติรูทอยู่ที่เลเวล 0 (ตำแหน่งคี่), ลูกซ้าย/ขวาของรูทอยู่ที่เลเวล 2, ลูกซ้ายเป็นตำแหน่งคี่ ลูกขวาเป็นตำแหน่งคู่ และไปเรื่อยๆ

ตัวอย่าง

        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

วิธีแก้

ใช้ Level Order Traversal ระหว่างการท่อง ให้ทำเครื่องหมายโหนดแรกเป็นตำแหน่งคี่ แล้วสลับเป็นคู่เมื่อเจอโหนดใหม่ และสลับกลับมาคี่ต่อไป และทำซ้ำ

ตัวอย่างโค้ด Java

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 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 queue = new LinkedList();
        queue.add(tree);
        System.out.println(difference(queue));
    }
}

ผลลัพธ์

11