Symmetric Tree

Một ảnh đối xứng qua gương đọc giống nhau từ trái sang phải và từ phải sang trái, vì vậy mỗi tầng, khi ghi rõ cả những vị trí trống, phải đọc giống nhau theo cả hai hướng. Trong ví dụ thứ hai, tầng dưới cùng đọc là -1 3 -1 3, khi đảo ngược thành 3 -1 3 -1, nên đáp án là false.

Các vị trí trống phải được giữ lại trong hàng: nếu không có chúng, tầng đó sẽ đọc là 3 3 và vượt qua bài kiểm tra. Các nút con của vị trí trống cũng là vị trí trống, vì vậy chỉ các nút thực mới thêm phần tử. Mỗi nút được duyệt một lần, tốn thời gian O(n), và mỗi lần chỉ lưu một tầng trong bộ nhớ, tốn O(w) với w là độ rộng của tầng rộng nhất.

So sánh cây con trái của nút gốc, ở chỉ số 1, với cây con phải của nút gốc, ở chỉ số 2. Hai vị trí đối xứng với nhau khi cả hai đều trống, hoặc khi cả hai chứa cùng một giá trị và các nút con của chúng bắt chéo nhau: nút con trái của vị trí này đối xứng với nút con phải của vị trí kia (cặp ngoài), còn nút con phải của vị trí này đối xứng với nút con trái của vị trí kia (cặp trong). Đó là định nghĩa của ảnh gương được áp dụng xuống thêm một mức, nên nếu mọi cặp đều khớp thì toàn bộ cây cũng đối xứng.

Mỗi nút thực thuộc nhiều nhất một cặp, nên thời gian chạy là O(n); ngăn xếp lời gọi có độ sâu bằng chiều cao của cây, O(h).

Đệ quy chỉ ghi nhớ các cặp còn chờ được kiểm tra, vì vậy hãy tự lưu chúng trên một ngăn xếp. Thứ tự kiểm tra không quan trọng, vì cây chỉ đối xứng nếu mọi cặp đều khớp: ngăn xếp tạo ra thứ tự duyệt theo chiều sâu, còn hàng đợi tạo ra thứ tự duyệt theo từng mức. Ví dụ thứ ba dừng ở cặp không khớp đầu tiên, (3, 6), chứa 5 và 9.

Mỗi nút thực thuộc tối đa một cặp, vì vậy độ phức tạp thời gian là O(n). Ngăn xếp chứa khoảng một cặp đang chờ cho mỗi mức trên đường đi hiện tại, nên độ phức tạp không gian là O(h).