114. Flatten Binary Tree to Linked List
Tags:
Medium
Skills:
React Deep Dive
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu bạn “Làm phẳng” một binary tree thành một Linked list sử dụng chính các node của cây, theo thứ tự preorder (root → left → right). Mỗi node chỉ dùng pointer right để liên kết, left luôn là null
Approach
left thành null Thứ tự preorder đảm bảo node root luôn đi trước các node con trái và phải, đúng với yêu cầu “làm phẳng” thành linked list
Time and space complexity
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15/**
16 Do not return anything, modify root in-place instead.
17 */
18function flatten(root: TreeNode | null): void {
19 let curr = root;
20 while(curr) {
21 if(curr.left) {
22 let prev = curr.left;
23 while(prev.right !== null) {
24 prev = prev.right;
25 }
26
27 prev.right = curr.right;
28 curr.right = curr.left;
29 curr.left = null
30 }
31 curr = curr.right
32 }
33};1while(prev.right !== null) {
2 prev = prev.right;
3}có ý nghĩa gì?
right (phải) trong một cấu trúc dữ liệu dạng cây (tree) hoặc danh sách liên kết (linked list) cho đến khi không còn nút con bên phải nữa.prev ban đầu trỏ đến một nút trong cây hoặc danh sách.prev.right không phải là null (tức là vẫn còn nút con bên phải).prev được cập nhật thành nút con bên phải (prev = prev.right), nghĩa là tiến sang nút kế tiếp bên phải.prev sẽ trỏ đến nút cuối cùng ở phía bên phải (nút không có con phải).curr = root;Bắt đầu từ node gốc.
while(curr) { ... }Lặp qua từng node, mỗi lần di chuyển sang phải.
if(curr.left) { ... }Nếu node hiện tại có con trái.
let prev = curr.left; while(prev.right !== null) { prev = prev.right; }Tìm node ngoài cùng bên phải của nhánh trái.
prev.right = curr.right;Nối nhánh phải hiện tại vào cuối nhánh trái.
curr.right = curr.left; curr.left = null;Đưa nhánh trái lên phải, xóa nhánh trái.
curr = curr.right;Di chuyển sang node tiếp theo (bây giờ là nhánh phải mới).