Trải phẳng cây nhị phân thành danh sách liên kết

Cho gốc root của một cây nhị phân, hãy trải phẳng cây thành một "danh sách liên kết" ngay trên chính các nút của cây:

• Danh sách dùng lại các nút TreeNode: con phải (right) trỏ tới nút kế tiếp, con trái (left) luôn là null.
• Thứ tự các nút trong danh sách là thứ tự duyệt tiền thứ tự (gốc, trái, phải) của cây ban đầu.

Hàm sửa trực tiếp cây và không trả về gì.

Hàm cần viết

Viết hàm flatten (không viết hàm main, không đọc dữ liệu vào): hệ thống gọi hàm với các tham số dưới đây và chấm giá trị của tham số sau khi gọi hàm.

Tham số:

• root (cây nhị phân): gốc của cây nhị phân (null khi cây rỗng), cho theo thứ tự tầng như LeetCode; hàm sửa trực tiếp cây này

Hàm không trả về gì: sửa trực tiếp root (cây nhị phân); hệ thống chấm giá trị của root sau khi gọi hàm. Sau lời gọi, cây là một “danh sách liên kết” dùng chính các nút của cây: con trái của mọi nút là null, con phải trỏ tới nút kế tiếp theo thứ tự duyệt tiền thứ tự (gốc, trái, phải) của cây ban đầu.

Ví dụ 1

Đầu vào

root = [1,2,5,3,4,null,6]

Đầu ra

[1,null,2,null,3,null,4,null,5,null,6]

Ví dụ 2

Đầu vào

root = []

Đầu ra

[]

Ví dụ 3

Đầu vào

root = [0]

Đầu ra

[0]

Ví dụ 4

Đầu vào

root = [10,20,null,30,40]

Đầu ra

[10,null,20,null,30,null,40]

Ghi chú

Hãy thử làm với bộ nhớ phụ $O(1)$.

Ràng buộc

• Số nút của cây nằm trong đoạn $[0, 2000]$.
• $-100 \le Node.val \le 100$