Đề 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 ở cấp độ lẻ và cấp độ chẵn. Giả sử gốc ở cấp độ 1, con trái/phải của gốc ở cấp độ 2, và cứ thế tiếp tục.
Ví dụ
5
/ \
2 6
/ \ \
1 4 8
/ / \
3 7 9
Tổng nút cấp độ lẻ = 5 + 1 + 4 + 8 = 18
Tổng nút cấp độ chẵn = 2 + 6 + 3 + 7 + 9 = 27
Chênh lệch = -9.
Giải pháp
Sử dụng Duyệt đệ quy (Recursive Traversal). Trong quá trình duyệt, trả về chênh lệch của nút gốc và nút con trái, phải của nó.
Ví dụ
Chương trình Java sau tìm kết quả yêu cầu.
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));
}
}
Kết quả
-9