Làm thế nào tôi có thể trả về một bool trong việc thực hiện đệ quy tìm kiếm chiều sâu đầu tiên?

Question

Tôi muốn viết một hàm để kiểm tra xem hai cây nhị phân có giống nhau hay không.

Mã này trông giống như:

bool checkSame(Node* first, Node* second) { 
    // Check if nodes are the same 

    // Check left nodes: checkSame(first->left, second->left) 
    // Check right nodes: checkSame(first->right, second->right) 

} 

Vấn đề là tôi không chắc chắn những gì để trở lại đây. Tất cả các triển khai của DFS tôi đã tìm thấy có một giá trị trả về void. Có một trong đó nó trả về một bool?

Ngoài ra, tôi đang tìm một giải pháp đệ quy, không phải là giải pháp lặp lại.

Answer 1

Bạn làm điều đó theo cách giống hệt như khi bạn đang gọi một số chức năng khác thay vì đệ quy.
(bí mật lớn Đệ quy là không có gì đặc biệt về đệ quy là.)

Cây cối đều bình đẳng khi và chỉ khi

• các nút đều bình đẳng, và
• cả subtrees của nó đều bình đẳng

vậy

return first->data == second->data 
    && checkSame(first->left, second->left) 
    && checkSame(first->right, second->right); 

Xử lý các thùng trống còn lại dưới dạng tập thể dục.