117. Populating Next Right Pointers in Each Node II
June 24, 2025
04:32 AM
No headings found
Loading content...
No headings found
Problem
Bài toán yêu cầu nối con trỏ next của mỗi node trong binary tree (không hoàn chỉnh) sang node bên phải cùng tầng. Nếu không có node bên phải thì next là null . Ban đầu tất cả các next đều là null
Phân tích & ý tưởng
next đã nối ở tầng hiện tại để duyệt tầng tiếp theo mà không cần queue phụApproach
prev để nhớ node trước đó ở tầng tiếp theo, và một biến next_level_head để nhớ node đầu tiên của tầng tiếp theoprev.next next_level_head next đã nối sẵn)Solution
1/**
2 * Definition for _Node.
3 * class _Node {
4 * val: number
5 * left: _Node | null
6 * right: _Node | null
7 * next: _Node | null
8 *
9 * constructor(val?: number, left?: _Node, right?: _Node, next?: _Node) {
10 * this.val = (val===undefined ? 0 : val)
11 * this.left = (left===undefined ? null : left)
12 * this.right = (right===undefined ? null : right)
13 * this.next = (next===undefined ? null : next)
14 * }
15 * }
16 */
17
18
19function connect(root: _Node | null): _Node | null {
20 if(!root) return null;
21 let curr: Node | null = root;
22 while(curr) {
23 let dummy = new Node(0);
24 let prev = dummy;
25
26 while(curr) {
27 if(curr.left) {
28 prev.next = curr.left;
29 prev = prev.next;
30 }
31
32 if(curr.right) {
33 prev.next = curr.right;
34 prev = prev.next;
35 }
36
37 curr = curr.next;
38 }
39 curr = dummy.next;
40 }
41
42 return root;
43};dummy để nối các node ở tầng tiếp theonext đã nối sẵndummy.next 1. dummy chỉ là điểm bắt đầu để nối chuỗi next của tầng tiếp theo
dummy chỉ là một node giả, không nằm trong cây gốc.prev ban đầu trỏ đến dummy, nhưng sau đó sẽ trỏ đến các node thật trong cây.2. prev sẽ lần lượt trỏ đến các node thật trong cây
prev.next = curr.left, bạn đã nối dummy.next đến node thật đầu tiên của tầng tiếp theo (ví dụ node 2).prev = prev.next, tức là prev bây giờ trỏ đến node 2 (node thật trong cây).prev.next = ..., bạn thực chất đang thay đổi trường next của node 2, node 5, node 7... (là các node thật trong cây).3. Chỉ có dummy là node giả, còn lại prev sẽ trỏ đến node thật
Việc dùng let dummy = new Node(0); trong thuật toán là để tạo một node giả (dummy node) giúp đơn giản hóa việc nối các node ở tầng tiếp theo.
Vì sao cần dummy node?
next của tầng tiếp theo một cách đơn giản không cần điều kiện đặc biệt cho node đầu tiênCách hoạt động
dummy.next sẽ luôn trỏ tới node đầu tiên của tầng tiếp theoprev bắt đầu từ dummy. Mỗi khi gặp node con (trái hoặc phải), bạn nối prev.next = node_con và cập nhật prev = prev.next curr = dummy.next để chuyển sang tầng tiếp theodummy và prev để nối tất cả các node con (trái/ phải) của các node ở tầng hiện tại lại với nhau bằng pointer next Giải thích chi tiết
Khi bắt đầu tầng 1:
curr đang trỏ vào node 1 (gốc).dummy là một node giả, prev = dummy.Trong vòng lặp while(curr):
curr.left và curr.right:curr.left là node 2 ⇒ prev.next = curr.left (tức là dummy.next = 2), rồi prev = prev.next = 2.curr.right là node 3 ⇒ prev.next = curr.right (tức là 2.next = 3), rồi prev = prev.next = 3.curr = curr.next (mà node 1 không có next, nên curr = null).Kết thúc vòng lặp:
dummy.next = curr.left ở bước đầu tiên của tầng này.Tóm lại:
curr = dummy.next, bạn bắt đầu duyệt tầng 2 từ node 2.Đúng
Khi bạn dùng prev.next = ... để nối các node ở tầng tiếp theo, bạn thực chất đang thay đổi tực tiếp trường next của các node trong cây con gốc (root)
Vì trong cây nhị phân, các node con đều là tham chiếu (reference) đến các node thực sự trong cây, nên mọi thay đổi qua next đều tác đọng đến chính các node đó trong cây root
Bản chất kỹ thuật
prev.next = ..., bạn đang cập nhật trường next của chính node đó trong cây gốc (root).next của các node trong cây gốc đều đã được cập nhật đúng.