Giá trị trả về của hàm đệ quy cần được xác định rõ ràng, cùng với các tham số đầu vào. Hiểu được cách giá trị được truyền ngược trở lại là bước quan trọng đầu tiên trong tư duy đệ quy, nếu không, bạn sẽ gặp lỗi ở các chi tiết dù có thể có đúng hướng chung.

1. Tìm Hiệu Tuyệt Đối Nhỏ Nhất Trong Cây Tìm Kiếm Nhị Phân

Với bài toán này, ta chỉ cần nhớ rằng duyệt trung thứ tự (in-order traversal) của cây nhị phân tìm kiếm là một dãy tăng dần. Do đó, hiệu tuyệt đối nhỏ nhất giữa hai nút luôn nằm giữa hai nút liền kề trong quá trình duyệt trung thứ tự. Giải pháp sử dụng con trỏ kép để xử lý tại mỗi bước duyệt.

/**
 * Định nghĩa một nút trong cây nhị phân.
 */
class Node {
    int giaTri;
    Node conTrai;
    Node conPhai;
    Node() {}
    Node(int giaTri) { 
        this.giaTri = giaTri; 
    }
    Node(int giaTri, Node conTrai, Node conPhai) {
        this.giaTri = giaTri;
        this.conTrai = conTrai;
        this.conPhai = conPhai;
    }
}

class GiaiPhap {
    int hieuNho = Integer.MAX_VALUE;
    Node truoc;
    
    public int timHieuNhoNhat(Node goc) {
        duyet(goc);
        return hieuNho;
    }
    
    private void duyet(Node nut) {
        if(nut == null) return;
        
        duyet(nut.conTrai);
        
        if(truoc != null) {
            hieuNho = Math.min(hieuNho, nut.giaTri - truoc.giaTri);
        }
        truoc = nut;
        
        duyet(nut.conPhai);
    }
}

2. Tìm Số Xuất Hiện Nhiều Nhất Trong Cây Tìm Kiếm Nhị Phân

Ngoài mảng kết quả, ta cần duy trì hai biến để theo dõi số lượng hiện tại và số lượng tối đa để quyết định khi nào cần cập nhật kết quả. Việc cập nhật có thể thực hiện ở cuối xử lý mỗi nút, tách biệt với việc thống kê số lượng.

class GiaiPhap {
    List<Integer> ketQua = new ArrayList<>();
    int soLuongMax;
    int giaTriTruoc;
    int dem;
    
    public int[] timCheDo(Node goc) {
        duyet(goc);
        return ketQua.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public void duyet(Node nut) {
        if(nut == null) return;
        
        duyet(nut.conTrai);
        
        if(nut.giaTri == giaTriTruoc) {
            dem++;
        } else {
            dem = 1;
        }
        giaTriTruoc = nut.giaTri;
        
        if(dem == soLuongMax) {
            ketQua.add(nut.giaTri);
        }
        if(dem > soLuongMax) {
            ketQua.clear();
            ketQua.add(nut.giaTri);
            soLuongMax = dem;
        }
        
        duyet(nut.conPhai);
    }
}

3. Tổ Tiên Chung Gần Nhất Trong Cây Nhị Phân

Để xác định một nút có phải là tổ tiên chung gần nhất không, ta cần kiểm tra xem cây con trái và cây con phải có thể tiếp cận đến nút p và q không, đồng thời tìm nút có độ sâu lớn nhất. Nút đầu tiên tìm được chính là tổ tiên chung cần tìm, và nên sử dụng duyệt hậu thứ tự (post-order traversal) để xử lý cây con trái và phải trước. Việc sử dụng kiểu Node thay vì true/false có thể truyền tải nhiều thông tin hơn (các nút đã gặp).

Điều kiện dừng đệ quy: nút null trả về null, nút là p hoặc q trả về nút đó (giá trị của nút không quan trọng, quan trọng là không null) để chỉ ra đường đi khả thi.

Sử dụng biến trái và phải để ghi nhận giá trị trả về từ cây con trái và phải.

Xử lý nút: nếu trái hoặc phải null, nghĩa là một đường đi không thể tiếp cận p hoặc q, trả về đường đi còn lại. Nếu cả hai đều null, trả về null. Nếu cả hai đều không null, nghĩa là nút này là tổ tiên chung của p và q, trả về chính nút này.

class GiaiPhap {
    public Node timToTienChung(Node goc, Node p, Node q) {
        if(goc == null) return null;
        
        if(goc == p || goc == q) {
            return goc;
        }
        
        Node conTrai = timToTienChung(goc.conTrai, p, q);
        Node conPhai = timToTienChung(goc.conPhai, p, q);
        
        if(conTrai == null) return conPhai;
        if(conPhai == null) return conTrai;
        
        return goc;
    }
}