# [543. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/description/?envType=daily-question&envId=2024-02-27)

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

Cho `root` (gốc) của một Cây nhị phân, tìm **đường kính** của cây.

**Đường kính** của một Cây nhị phân là **độ dài** của đường đi dài nhất giữa 2 đỉnh bất kỳ trong cây. Đường đi này *không nhất thiết* đi qua `root`.

**Độ dài** của một đường đi là số *cạnh* trên đường đi.

### Giới hạn

$n =$ số đỉnh trong cây
$k =$ giá trị của đỉnh

- $1 \le n \le 10^4$
- $-100 \le k \le 100$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n)$**

Với mỗi đỉnh `node` trong cây, giả sử đường kính cần tìm đi qua đỉnh đó thì ta tính bằng công thức `diameter = maxDepth(node.left) + maxDepth(node.right)`, với `maxDepth(node)` là độ sâu max trong các lá của cây con gốc `node` (hoặc bạn cũng có thể nghĩ là độ cao của cây con gốc `node`)

Vì đường kính cần tìm không nhất thiết đi qua `root` cho sẵn nên ta sẽ phải lấy max các đường kính đi qua các đỉnh trong cây.

# 3. Lời giải chi tiết

Làm như trên, chỉ lưu ý rằng code làm sao cho không bị lỗi :v (lưu ý định nghĩa **độ dài** đường đi ở trên)

### [Code mẫu](https://leetcode.com/problems/diameter-of-binary-tree/submissions/1187649572?envType=daily-question&envId=2024-02-27)

### Độ phức tạp thuật toán

Thời gian: $O(n)$

Bộ nhớ mở rộng: $O(h)$
($h$ là độ cao của cây; bộ nhớ mở rộng được tính bằng cách xác định độ sâu tối đa của phép đệ quy)

# 4. Kết luận & Gợi ý mở rộng

Một bài Easy cá nhân mình thấy không dễ cho lắm, đặc biệt là nếu bạn không quen code giải thuật trên CTDL Cây hoặc code đệ quy. Đến cả ý tưởng cũng không phải ở mức dễ nghĩ ra được.

Mời các bạn giải bài (không) Hard sau để vận dụng kỹ thuật vừa học được:
[124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)