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

โจทย์

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

วิธีแก้

ใช้ Recursive 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