# [129. Sum Root to Leaf Number](https://leetcode.com/problems/sum-root-to-leaf-numbers/description/?envType=daily-question&envId=2024-04-15)

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

Cho một cây nhị phân, mỗi nút chứa một số từ `0` đến `9`.

Mỗi đường đi từ gốc đến lá tạo ra một số.

- Ví dụ, đường đi từ gốc đến lá `3->2->5` tạo ra số `325`.

Tìm *tổng của tất cả các số tạo ra* từ các đường đi từ gốc đến lá.

Nút **lá** là các nút mà không có con nào.

### Giới hạn

$n =$ Tổng số nút trong cây
$k =$ `node.val`
$h =$ [Độ sâu](https://www.geeksforgeeks.org/height-and-depth-of-a-node-in-a-binary-tree/) tối đa của cây

- $1 \le n \le 1000$
- $0 \le k \le 9$
- $1 \le h \le 10$

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

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

Trước hết, để giải được bài này, bạn chỉ cần có kiến thức về [các cách duyệt cây](https://vi.wikipedia.org/wiki/Duy%E1%BB%87t_c%C3%A2y#Duy%E1%BB%87t_c%C3%A2y_nh%E1%BB%8B_ph%C3%A2n).

Còn lại trong khi duyệt, ta có thể thêm một biến để theo dõi số đang được tạo ra khi ta duyệt theo đường đi hiện tại.

Có thể thấy vì ta bắt buộc phải duyệt hết các nút trong cây, độ phức tạp thời gian tối ưu nhất có thể đạt được là tuyến tính ($O(n)$). Vậy thì mục tiêu đang không phải tối ưu độ phức tạp thời gian, ta có thể tối ưu độ phức tạp *bộ nhớ* được không?

Thay vì sử dụng kỹ thuật duyệt cây thông thường cần $O(h)$ bộ nhớ ngoài (để lưu stack của đường duyệt), mình xin giới thiệu một cách duyệt *không cần dùng stack hay đệ quy*: **[Morris Traversal](https://www.educative.io/answers/what-is-morris-traversal)**.

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

## Cách 1: DFS (Preorder Traversal)

Ở đây mình sẽ sử dụng đệ quy để duyệt. Cách làm rất đơn giản:

- Với hàm DFS ta lưu thêm một biến số nguyên `path` nữa để lưu số được tạo ra khi duyệt đến `node`
- Thứ tự xử lý là `node -> node.left -> node.right`
- Ta xử lý `node` trước (cập nhật số nguyên `path`)
- Kiểm tra xem `node` có là nút lá không
- Nếu là nút lá, cộng `path` vào biến lưu kết quả `res` và ngừng duyệt đường đi hiện tại
- Gọi đệ quy hàm DFS cho `node.left` và `node.right`.

### [Code mẫu](https://leetcode.com/problems/sum-root-to-leaf-numbers/submissions/1232699589?envType=daily-question&envId=2024-04-15)

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

Thời gian: $O(n)$

Bộ nhớ mở rộng: $O(h)$

## Cách 2: Morris Traversal

Với các cách duyệt cây thông thường, ta cần dùng stack hoặc đệ quy để trở về các nút cha để duyệt cây con còn lại của chúng. Ví dụ, ta duyệt hết cây con bên trái của nút thì ta phải có cách trở lại nút để duyệt cây con bên phải của nó.

Ý tưởng của duyệt cây Morris là sử dụng những *con trỏ* (temporary link) giữa một nút lá `node` và tổ tiên `curr` của nó:

- `node.right = curr`

Vậy khi duyệt đến nút lá `node`, ta xác định tổ tiên `curr` của nó và xem mối liên hệ có đang tồn tại không:

- **Không tồn tại:** Đặt con trỏ (đặt `node.right` trỏ đến `curr`) và trở về `curr` để duyệt sang cây con bên **trái**.
- **Tồn tại:** Bỏ con trỏ (`node.right = NULL`), trở về `curr` và duyệt sang cây con bên **phải**.

Vậy nếu `curr` không có con trái (không có cây con bên trái) thì sao? Trong trường hợp đó, ta lập tức duyệt sang cây con bên phải.

Pseudo-code dành cho thuật toán duyệt cây Morris:

curr = root
while curr is not NULL:
    if curr.left is not NULL:
        node = curr.left
        while node.right is not NULL and node.right != curr:
            node = node.right
            
        if node.right is NULL:
            node.right = curr
            curr = curr.left
        else:
            node.right = NULL
            visit(curr)
            curr = curr.right       
    else:
        visit(curr)
        curr = curr.right  

Để hiểu rõ hơn về thuật toán, ta làm việc trên ví dụ sau:


`curr` được khởi tạo là nút gốc $4$.

`curr` có con trái, vì vậy nó sẽ được trỏ đến bởi **con phải ngoài cùng của cây con trái** (hay nói cách khác, là nút cuối cùng được duyệt đến khi duyệt cây con trái theo thứ tự Inorder).

Ta làm tương tự với cây con trái có nút gốc là $2$. Kết quả là như hình dưới đây:


Với `curr` được đặt ở nút $2$, `curr` có con trái và con phải ngoài cùng của nó đã trỏ đến `curr`. Ta tiếp tục đặt `curr` ở nút $1$. Nút $1$ là nút lá, và nó trỏ đến $2$ qua con trỏ `right`.


Ta `visit` $1$ vì nó không có con trái, và `curr` trở lại về $2$. Tại vòng lặp tiếp theo, vì $1$ vẫn đang trỏ đến $2$, ta xác định được cây con bên trái của $2$ đã được duyệt, vì vậy ta xoá bỏ con trỏ, `visit` $2$ và đặt `curr` sang $3$, là ta bắt đầu duyệt cây con bên phải của $2$.

Theo cùng logic, $3$ được `visit`, `curr` trở về $4$ và cây con bên trái của $4$ được xác định là đã được duyệt,...

Với thuật toán duyệt được xác định, ta chỉ cần biến tấu để giải được bài toán. Lưu ý rằng vì thứ tự duyệt sẽ là Inorder thay vì Preorder của DFS nên ta sẽ phải xử lý `path` khác một chút.

### [Code mẫu](https://leetcode.com/problems/sum-root-to-leaf-numbers/submissions/1232765124?envType=daily-question&envId=2024-04-15)

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

Thời gian: $O(n)$

(Ta có thể thấy rằng mỗi cạnh của cây sẽ được đi qua nhiều nhất là 3 lần, chưa kể sẽ có những "cạnh" mới được tạo ra trong quá trình. Tuy nhiên, trong trường hợp xấu nhất, độ phức tạp thời gian sẽ chưa đạt đến đa thức $O(n^2)$)

Bộ nhớ mở rộng: $O(1)$

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

Một bài đầu tuần nhẹ nhàng nhưng cũng không kém thú vị.

Một số bài mở rộng liên quan đến duyệt cây và đường đi (path):

- [112. Path Sum](https://leetcode.com/problems/path-sum/)
- [988. Smallest String Starting From Leaf](https://leetcode.com/problems/smallest-string-starting-from-leaf/)
- [124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)