173. Binary Search Tree Iterator
Tags:
Medium
Skills:
Tree
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 thực hiện một iterator để duyệt cây nhị phân tìm kiếm (BST) theo thứ tự tăng dần (in-order). Bạn cần thực hiện 3 hàm chính
- BSTIterator(root): Khởi tạo iterator với node gốc
- next(): Trả về số nhỏ nhất tiếp theo trong BST → Loại phần tử ra luôn
- hasNext(): Trả về true nếu còn phần tử chưa duyệt
Yêu cầu về độ phức tạp:
- Mỗi lần gọi next() và hasNext() trung bình O(1) thời gian.
- Bộ nhớ phụ tối đa O(h), với h là chiều cao cây.
Approach
Sử dụng một stack để lưu vết các node bên trái khi đi xuống cây, giống như cách duyệt in-order không đệ quy.
Khi khởi tạo, ta đẩy tất cả các node bên trái từ root xuống leaf vào stack.
Khi gọi next(), pop node trên cùng ra (node nhỏ nhất chưa duyệt), nếu node này có con phải thì đẩy tất cả các node bên trái của con phải vào stack
Ưu điểm
- Đảm bảo next() luôn return về node nhỏ nhất còn lại
- hasNext() chỉ cần kiểm tra stack còn phần tử không
- Độ phức tạp thỏa mãn yêu cầu đề bài
Time and space complexity
Solution
typescripttypescript
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
15class BSTIterator {
16 stack: TreeNode[] = []
17
18 constructor(root: TreeNode | null) {
19 this.pushLeft(root);
20 }
21
22 pushLeft(node: TreeNode | null): void {
23 while (node) {
24 this.stack.push(node);
25 node = node.left;
26 }
27 }
28
29 next(): number {
30 const node = this.stack.pop();
31 if (node.right) {
32 this.pushLeft(node.right)
33 }
34 return node.val
35 }
36
37 hasNext(): boolean {
38 return this.stack.length > 0
39 }
40}
41
42/**
43 * Your BSTIterator object will be instantiated and called as such:
44 * var obj = new BSTIterator(root)
45 * var param_1 = obj.next()
46 * var param_2 = obj.hasNext()
47 */💡
Tóm tắt
- Khởi tạo
- Đẩy toàn bộ nhánh trái từ root vào stack
- next()
- Pop node trên cùng (nhỏ nhất), nếu có con phải thì đẩy tiếp nhánh trái của con phải vào stack
- hasNext()
- Stack còn phần tử nghĩa là còn node chưa duyệt