---
# System prepended metadata

title: 100. Same Tree

---

# 100. Same Tree

## Tóm tắt đề bài

- Cho 2 cây `q` và `p`, kiểm tra xem chúng có giống hệt nhau (identical) hay không.

### Giới hạn
- Số node ở mỗi cây trong khoảng [0, 100].
- -10^4 <= Node.val <= 10^4

## Lời giải
- Ta sẽ sử dụng đệ quy:
    - Nếu cả 2 cây đều rỗng (null), trả về true => **base case**
    - Nếu chỉ 1 trong 2 cây rỗng, hoặc node hiện tại của 2 cây khác nhau, trả về false.
    - Nếu không, ta đệ quy xuống cây con trái và phải của 2 cây và check xem chúng giống nhau không.

### Độ phức tạp thuật toán
Gọi **N1, N2** là số node của từng cây.
Gọi **H1, H2** là chiều cao (height) của từng cây.

Thời gian: $O(min(N1, N2))$
Bộ nhớ: $O(min(H1, H2))$

### Code tham khảo
https://leetcode.com/problems/same-tree/submissions/1186326625/?envType=daily-question&envId=2024-02-26
