Đến nội dung chính
Sổ ôn Backend

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánMid32 phút đọc

Luyện phỏng vấn: cây nhị phân, BST và heap trong Java

Ôn 13 thẻ
Trong bài này

Cả bài trong một trang: ý chính, sơ đồ, điểm phỏng vấn.

Luyện phỏng vấn: cây nhị phân, BST và heap trong Java

1Duyệt cây nhị phân

Mỗi nút có tối đa hai con. DFS đi sâu bằng stack (hoặc call stack), BFS đi từng tầng bằng queue.

Cách duyệt Thứ tự Dùng khi
Preorder gốc, trái, phải sao chép, serialize
Inorder trái, gốc, phải BST ra dãy tăng
Postorder trái, phải, gốc chiều cao, xoá cây
Level order từng tầng in theo tầng, gần gốc nhất

2Khuôn hỏi hai con rồi gộp

Hầu hết bài cây là đệ quy hỏi hai con rồi gộp: chiều cao, đường kính, LCA đều O(n). Cây lệch sâu n thì dùng stack tường minh.

flowchart TD
  Q{"Đề hỏi gì?"} -->|"Thông tin cả cây"| R["Đệ quy: hỏi hai con, gộp"]
  Q -->|"Theo tầng, gần gốc"| B["BFS với queue"]
  Q -->|"BST, có thứ tự"| I["Inorder hoặc khoảng min-max"]
  Q -->|"K lớn nhất"| H["Heap kích thước K"]
  Q -->|"Median luồng số"| T["Hai heap"]

3Kiểm tra BST bằng khoảng

BST: mọi nút trái nhỏ hơn, mọi nút phải lớn hơn cả cây con. Truyền khoảng (low, high) xuống, không chỉ so với con trực tiếp.

boolean valid(TreeNode n, long low, long high) {
    if (n == null) return true;
    if (n.val <= low || n.val >= high)
        return false;
    return valid(n.left, low, n.val)
        && valid(n.right, n.val, high);
}

4Heap và PriorityQueue

Heap là cây gần đầy đủ lưu trong mảng, cha luôn nhỏ hơn con (min-heap). Xem nhỏ nhất O(1), thêm hoặc lấy O(log n).

  • new PriorityQueue<>() mặc định là min-heap
  • Max-heap: Comparator.reverseOrder()
  • remove(o) bất kỳ là O(n): tránh trong vòng lặp
  • Duyệt bằng for không ra thứ tự; phải poll() lần lượt

5Top-K, median, TreeMap

Giữ min-heap kích thước K để lấy K số lớn nhất: gốc là số cần vứt đi. Cần "gần x nhất" trên tập đang đổi thì dùng TreeMap.

Bài toán Cách Chi phí
Top-K lớn nhất Min-heap kích thước K O(n log K)
Median luồng số Max-heap + min-heap Thêm O(log n)
Gộp K danh sách Heap các đầu danh sách O(N log k)
Lân cận ≤ x, ≥ x TreeMap floor, ceiling O(log n)

💡 Ghi nhớ

  • DFS tốn O(chiều cao), BFS tốn O(độ rộng).

  • Inorder của BST ra dãy tăng: dùng tìm phần tử nhỏ thứ k.

  • Hai heap của median lệch nhau tối đa một phần tử.

  • Dữ liệu ở DB: để ORDER BY ... LIMIT K có index làm.

⭐ Điểm phỏng vấn

Tự trả lời trước, rồi bấm từng câu để xem đáp án.

  • PriorityQueue là min hay max-heap?

    Min-heap; max-heap truyền reverseOrder().

  • 100 số lớn nhất trong 10 triệu?

    Min-heap kích thước 100, O(n log K).

  • Median luồng quá lớn cho RAM?

    Đếm bucket hoặc t-digest, HDRHistogram.

⚠️ Lỗi thường gặp

  • Đệ quy trên cây lệch 100.000 nút: StackOverflowError.

  • Comparator viết b - a: tràn số, heap xếp nhầm không báo lỗi.

  • Kiểm tra BST chỉ so cha với con trực tiếp.

Cụm bài Luyện phỏng vấn thuật toán: 1. Cây và heap · 2. Đồ thị và quy hoạch động

Chín bài phỏng vấn hay gặp về cây nhị phân, cây tìm kiếm nhị phân (BST) và heap, mỗi bài có đề diễn đạt lại, cách nhận dạng, lời giải Java 21 đã chạy thử, độ phức tạp và edge case. Đọc xong, bạn nhìn đề là biết nên đệ quy, BFS hay dùng PriorityQueue. Nên đọc trước: đệ quy và call stack, stack và queue, TreeMap và Comparator.

Sơ đồ tóm tắt:

flowchart TD
  Q{"Đề hỏi gì?"} -->|"Thông tin cả cây"| R["Đệ quy: hỏi hai con, gộp"]
  Q -->|"Theo tầng, gần gốc nhất"| B["BFS với queue"]
  Q -->|"Có thứ tự, BST"| I["Inorder hoặc khoảng min-max"]
  Q -->|"K lớn nhất, nhỏ nhất"| H["Heap kích thước K"]
  Q -->|"Median luồng số"| T["Hai heap"]
  Q -->|"Tìm khoảng gần nhất"| M["TreeMap floor, ceiling"]
  R --> S["Cây lệch: dùng stack tường minh"]

1. Cây nhị phân: duyệt và đệ quy

Ý chính: bốn cách duyệt (preorder, inorder, postorder, level order) và một khuôn đệ quy dùng cho gần hết các bài. Viết được cả bản dùng stack, vì người phỏng vấn hay hỏi tiếp “bỏ đệ quy đi”.

Cây nhị phân: mỗi nút có tối đa hai con, left và right. Các bài dưới dùng chung class nút này:

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
Cách duyệt Thứ tự Dùng khi
Preorder gốc, trái, phải sao chép cây, serialize
Inorder trái, gốc, phải BST ra dãy tăng
Postorder trái, phải, gốc tính từ dưới lên: chiều cao, xoá cây
Level order từng tầng, trái sang phải khoảng cách tới gốc, in theo tầng

1.1. Duyệt inorder và preorder (tương tự LeetCode 94, 144)

Đề: cho gốc của một cây nhị phân, trả về danh sách giá trị theo thứ tự inorder (và preorder). Làm cả bản không đệ quy.

Ý tưởng: bản đệ quy chép định nghĩa. Bản lặp thay call stack bằng ArrayDeque (xem vì sao không dùng Stack): inorder đi trái hết cỡ, lấy ra, rẽ phải; preorder đẩy con phải trước để con trái ra trước.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static List<Integer> inorderIterative(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {          // go as far left as possible
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();             // leftmost unvisited node
            out.add(cur.val);
            cur = cur.right;               // then its right subtree
        }
        return out;
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }


    public static void main(String[] args) {
        check("[1, 2, 3, 4, 5, 6, 7]", inorderIterative(sample()));
        check("[]", inorderIterative(null));
        check("[1, 2, 3]", inorderIterative(new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3)))));
    }
}
Bản đệ quy và preorder bằng stack
import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static List<Integer> inorderRecursive(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        inorder(root, out);
        return out;
    }
    private static void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    static List<Integer> preorderIterative(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            out.add(node.val);
            if (node.right != null) stack.push(node.right); // right first so left pops first
            if (node.left != null) stack.push(node.left);
        }
        return out;
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check("[1, 2, 3, 4, 5, 6, 7]", inorderRecursive(sample()));
        check("[4, 2, 1, 3, 6, 5, 7]", preorderIterative(sample()));
        check("[]", preorderIterative(null));
    }
}

Postorder bằng stack khó hơn một chút. Mẹo nhanh: chạy preorder kiểu “gốc, phải, trái” rồi đảo ngược kết quả.

Độ phức tạp: O(n) thời gian, O(h) bộ nhớ với h là chiều cao cây: O(log n) nếu cây cân bằng, O(n) nếu cây lệch.

Edge case: cây rỗng; cây lệch hẳn một phía.

1.2. Duyệt theo tầng (tương tự LeetCode 102)

Đề: trả về giá trị các nút theo từng tầng, mỗi tầng là một danh sách, từ trái sang phải.

Ý tưởng: BFS với queue. Mẹo quan trọng: đọc queue.size() trước vòng for, đó chính là số nút của tầng hiện tại.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();               // nodes on the current level
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            levels.add(level);
        }
        return levels;
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check("[[4], [2, 6], [1, 3, 5, 7]]", levelOrder(sample()));
        check("[]", levelOrder(null));
        check("[[1], [2], [3]]", levelOrder(new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3)))));
    }
}

Độ phức tạp: O(n) thời gian, O(w) bộ nhớ với w là độ rộng lớn nhất (cỡ n/2 ở tầng cuối cây đầy đủ).

Edge case: cây rỗng; cây lệch. Cùng khuôn: nhìn cây từ bên phải, duyệt zigzag, độ sâu nhỏ nhất.

1.3. Chiều cao và đường kính (tương tự LeetCode 104, 543)

Đề: tính chiều cao của cây (số nút trên đường dài nhất từ gốc tới lá), và đường kính (số cạnh của đường dài nhất giữa hai nút bất kỳ).

Ý tưởng: khuôn “hỏi hai con rồi gộp”. Đường dài nhất đi qua một nút dài height(trái) + height(phải) cạnh; tính chiều cao từ dưới lên và cập nhật kỷ lục trên đường đi, chỉ một lần duyệt.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    static int diameter(TreeNode root) {
        int[] best = {0};
        height(root, best);
        return best[0];
    }
    private static int height(TreeNode node, int[] best) {
        if (node == null) return 0;
        int l = height(node.left, best);
        int r = height(node.right, best);
        best[0] = Math.max(best[0], l + r);   // longest path through this node (in edges)
        return 1 + Math.max(l, r);
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check(3, maxDepth(sample()));
        check(4, diameter(sample()));
        check(0, diameter(new TreeNode(1)));
        // longest path (4-3-2-5-6) does not pass through the root 1
        TreeNode offRoot = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4), null),
                                                       new TreeNode(5, null, new TreeNode(6))), null);
        check(4, diameter(offRoot));
    }
}

Độ phức tạp: O(n) thời gian, O(h) bộ nhớ. Gọi maxDepth riêng cho từng nút thì thành O(n²) với cây lệch.

Edge case: đường kính không nhất thiết đi qua gốc; cây một nút có đường kính 0.

2. Cây tìm kiếm nhị phân (BST)

Ý chính: BST là cây mà mọi nút bên trái nhỏ hơn, mọi nút bên phải lớn hơn cả cây con, không chỉ con trực tiếp. Tính chất này cho inorder ra dãy tăng và cho phép bỏ một nửa cây ở mỗi bước, như tìm kiếm nhị phân.

Tìm, thêm, xoá trên BST tốn O(h): O(log n) khi cân bằng, O(n) khi lệch (thêm một dãy đã sắp xếp là ra “danh sách liên kết”). Vì vậy thư viện dùng cây tự cân bằng: TreeMap là cây đỏ đen (red-black tree).

2.1. Kiểm tra một cây có phải BST (tương tự LeetCode 98)

Đề: cho một cây nhị phân, kiểm tra nó có phải BST hợp lệ với giá trị không trùng.

Ý tưởng: mỗi nút phải nằm trong khoảng mở (low, high) do tổ tiên đặt ra. Sang trái thì cận trên thành giá trị nút; sang phải thì cận dưới thành giá trị đó. Cận kiểu long để xử đúng nút mang Integer.MIN_VALUE/MAX_VALUE.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private static boolean valid(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check(true, isValidBST(sample()));
        // 3 sits in the right subtree of 5: every parent-child pair looks fine, but it's not a BST
        check(false, isValidBST(new TreeNode(5, new TreeNode(4), new TreeNode(6, new TreeNode(3), new TreeNode(7)))));
        check(false, isValidBST(new TreeNode(2, new TreeNode(2), null)));
        check(true, isValidBST(new TreeNode(Integer.MAX_VALUE, new TreeNode(Integer.MIN_VALUE), null)));
    }
}

Độ phức tạp: O(n) thời gian, O(h) bộ nhớ. Cách khác: duyệt inorder, kiểm tra dãy tăng ngặt.

Edge case: cây rỗng là BST; giá trị trùng là không hợp lệ; giá trị biên của int.

2.2. Tổ tiên chung gần nhất (tương tự LeetCode 236, 235)

Đề: cho hai nút p, q trong cây, tìm tổ tiên chung thấp nhất (LCA, lowest common ancestor), tức nút sâu nhất có cả p và q trong cây con của nó (một nút được tính là tổ tiên của chính nó).

Ý tưởng với cây thường: hỏi hai con. Cả hai bên đều thấy một nút thì nút hiện tại là điểm rẽ, chính là LCA; chỉ một bên thấy thì đẩy kết quả bên đó lên.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        if (left != null && right != null) return root; // p and q on different sides
        return left != null ? left : right;
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        TreeNode root = sample();
        TreeNode n1 = root.left.left, n3 = root.left.right, n7 = root.right.right;
        check(2, lca(root, n1, n3).val);
        check(4, lca(root, n1, n7).val);
        check(2, lca(root, root.left, n3).val);   // one node is the ancestor of the other
    }
}

Ý tưởng với BST: cả hai giá trị nhỏ hơn nút thì đi trái, cả hai lớn hơn thì đi phải, còn lại là điểm rẽ.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static TreeNode lcaBST(TreeNode root, int p, int q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p < cur.val && q < cur.val) cur = cur.left;
            else if (p > cur.val && q > cur.val) cur = cur.right;
            else return cur;                 // split point
        }
        return null;
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check(6, lcaBST(sample(), 5, 7).val);
        check(4, lcaBST(sample(), 1, 7).val);
        check(2, lcaBST(sample(), 2, 3).val);
    }
}

Độ phức tạp: cây thường O(n) thời gian, O(h) stack; BST O(h) thời gian, O(1) bộ nhớ.

Edge case: p là tổ tiên của q (trả p); lời giải giả định cả hai nút có trong cây, nếu không chắc thì phải đếm số nút tìm thấy.

3. Heap và PriorityQueue

Ý chính: heap là cây nhị phân gần đầy đủ, cha luôn nhỏ hơn (min-heap) hoặc lớn hơn (max-heap) các con, lưu trong một mảng. Xem phần tử nhỏ nhất O(1), thêm/lấy O(log n): rẻ hơn giữ cả dãy luôn sắp xếp.

Trong mảng, nút i có con ở 2i + 1, 2i + 2, cha ở (i - 1) / 2. Thêm thì đặt cuối mảng rồi “nổi lên”; lấy gốc thì đưa phần tử cuối lên gốc rồi “chìm xuống”. Xây heap từ n phần tử có sẵn tốn O(n).

Việc Cách viết Java
Min-heap số new PriorityQueue<Integer>()
Max-heap số new PriorityQueue<Integer>(Comparator.reverseOrder())
Heap theo trường new PriorityQueue<>(Comparator.comparingInt(Task::priority))
Thêm, lấy, xem offer O(log n), poll O(log n), peek O(1)
Xoá phần tử bất kỳ remove(o) O(n): tránh dùng trong vòng lặp

3.1. Phần tử lớn thứ K và top-K phổ biến nhất (tương tự LeetCode 215, 347)

Đề: (a) cho mảng số, tìm phần tử lớn thứ k (tính cả trùng lặp). (b) cho mảng số, trả về k giá trị xuất hiện nhiều nhất.

Ý tưởng: giữ min-heap kích thước k. Gốc heap là số nhỏ nhất trong k số lớn nhất đã thấy, gặp số lớn hơn thì gốc bị đẩy ra. Nghe ngược nhưng đúng: thứ cần vứt đi là cái nhỏ nhất.

import java.util.*;

public class Main {
    static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();  // keeps the k largest seen so far
        for (int x : nums) {
            minHeap.offer(x);
            if (minHeap.size() > k) minHeap.poll();              // drop the smallest
        }
        return minHeap.peek();
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check(5, kthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
        check(4, kthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
        check(1, kthLargest(new int[]{3, 1, 2}, 3));
    }
}
Lời giải top-K phổ biến nhất

Đếm tần suất bằng HashMap.merge, rồi áp đúng khuôn heap kích thước k, so sánh theo số lần xuất hiện.

import java.util.*;

public class Main {
    static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);
        PriorityQueue<Map.Entry<Integer, Integer>> heap =
                new PriorityQueue<>(Map.Entry.comparingByValue());  // min-heap by count
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            heap.offer(e);
            if (heap.size() > k) heap.poll();
        }
        int[] out = new int[heap.size()];
        for (int i = out.length - 1; i >= 0; i--) out[i] = heap.poll().getKey(); // most frequent first
        return out;
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check("[1, 2]", Arrays.toString(topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
        check("[7]", Arrays.toString(topKFrequent(new int[]{7}, 1)));
    }
}

Độ phức tạp O(n + m log k) với m là số giá trị khác nhau. Có cách O(n) bằng bucket sort: mảng List[] đánh chỉ số theo tần suất (tần suất không vượt quá n), rồi đi từ cuối về.

Độ phức tạp: O(n log k) thời gian, O(k) bộ nhớ.

Edge case: k = n (trả số nhỏ nhất); có trùng lặp; k lớn hơn số phần tử.

3.2. Gộp K danh sách đã sắp xếp (tương tự LeetCode 23)

Đề: cho k danh sách liên kết, mỗi danh sách đã tăng dần, gộp thành một danh sách tăng dần.

Ý tưởng: heap chứa nút đầu của mỗi danh sách. Lấy nút nhỏ nhất ra nối vào kết quả, rồi đẩy nút kế tiếp của nó vào heap; heap không bao giờ quá k phần tử. Đây là bước “gộp k đường” của external sort.

import java.util.*;

public class Main {
    static class ListNode {
        int val; ListNode next;
        ListNode(int val) { this.val = val; }
    }
    static ListNode list(int... vals) {
        ListNode dummy = new ListNode(0), cur = dummy;
        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }
        return dummy.next;
    }
    static List<Integer> toList(ListNode node) {
        List<Integer> out = new ArrayList<>();
        for (; node != null; node = node.next) out.add(node.val);
        return out;
    }

    static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
        for (ListNode head : lists) if (head != null) heap.offer(head);
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            tail.next = smallest;
            tail = smallest;
            if (smallest.next != null) heap.offer(smallest.next);
        }
        return dummy.next;
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check("[1, 1, 2, 3, 4, 4, 5, 6]", toList(mergeKLists(new ListNode[]{list(1, 4, 5), list(1, 3, 4), list(2, 6)})));
        check("[]", toList(mergeKLists(new ListNode[]{})));
        check("[1, 2]", toList(mergeKLists(new ListNode[]{null, list(1, 2)})));
    }
}

Độ phức tạp: O(N log k) với N là tổng số nút; O(k) bộ nhớ.

Edge case: mảng rỗng; phần tử null trong mảng (offer(null) ném NullPointerException); chỉ một danh sách.

3.3. Median của một luồng số (tương tự LeetCode 295)

Đề: thiết kế class nhận số lần lượt (addNum) và trả median (số ở giữa) của tất cả số đã nhận bất cứ lúc nào (findMedian).

Ý tưởng: nửa nhỏ để trong max-heap low, nửa lớn trong min-heap high. Giữ hai điều kiện: mọi số trong low ≤ mọi số trong high, và low nhiều hơn high tối đa một phần tử. Median nằm ở hai gốc.

Lời giải MedianFinder và kiểm chứng ngẫu nhiên
import java.util.*;

public class Main {
    static class MedianFinder {
        private final PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap
        private final PriorityQueue<Integer> high = new PriorityQueue<>();                         // min-heap

        void addNum(int num) {
            low.offer(num);
            high.offer(low.poll());              // the largest of the low half moves up
            if (high.size() > low.size()) low.offer(high.poll()); // low may hold one extra
        }

        double findMedian() {
            if (low.size() > high.size()) return low.peek();
            return ((long) low.peek() + high.peek()) / 2.0;
        }
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(1); check(1.0, mf.findMedian());
        mf.addNum(2); check(1.5, mf.findMedian());
        mf.addNum(3); check(2.0, mf.findMedian());
        MedianFinder big = new MedianFinder();
        big.addNum(Integer.MAX_VALUE); big.addNum(Integer.MAX_VALUE);
        check((double) Integer.MAX_VALUE, big.findMedian());   // no int overflow
    }
}

Mẹo “luôn đi qua low rồi đẩy lên high” giúp không phải viết nhánh if so sánh num với hai gốc: điều kiện thứ tự giữa hai nửa tự đúng. Mình kiểm chứng bằng cách thêm 2.000 số ngẫu nhiên trong khoảng [-1000, 1000] và sau mỗi lần thêm so với median tính bằng sort: khớp hết.

Độ phức tạp: addNum O(log n), findMedian O(1), bộ nhớ O(n).

Edge case: cộng hai số lớn bị tràn: ép sang long trước khi cộng; gọi findMedian khi chưa có số nào.

4. TreeMap: BST cân bằng có sẵn

Ý chính: cần “phần tử gần nhất ≤ x hoặc ≥ x” trên một tập đang thay đổi thì dùng TreeMap/TreeSet: mọi thao tác O(log n), có sẵn floorKey, ceilingKey, headMap, tailMap. API chi tiết ở bài TreeMap, Comparator và Iterator.

4.1. Lịch đặt phòng không chồng giờ (tương tự LeetCode 729)

Đề: thiết kế lịch nhận yêu cầu đặt khoảng [start, end). Nhận nếu khoảng không chồng lên khoảng nào đã đặt, ngược lại từ chối.

Ý tưởng: lưu start → end trong TreeMap. Khoảng mới chỉ có thể đụng hai hàng xóm: khoảng bắt đầu ngay trước (floorEntry) và ngay sau (ceilingKey).

import java.util.*;

public class Main {
    static class MyCalendar {
        private final TreeMap<Integer, Integer> bookings = new TreeMap<>(); // start -> end, [start, end)

        boolean book(int start, int end) {
            Map.Entry<Integer, Integer> before = bookings.floorEntry(start);
            if (before != null && before.getValue() > start) return false;  // previous one runs into us
            Integer nextStart = bookings.ceilingKey(start);
            if (nextStart != null && nextStart < end) return false;         // we run into the next one
            bookings.put(start, end);
            return true;
        }
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        MyCalendar cal = new MyCalendar();
        check(true, cal.book(10, 20));
        check(false, cal.book(15, 25));   // overlaps [10, 20)
        check(true, cal.book(20, 30));    // touching the edge is fine
        check(false, cal.book(12, 13));   // fully inside
    }
}

Độ phức tạp: O(log n) mỗi lần đặt (danh sách thường: O(n)).

Edge case: khoảng chạm mép ([10, 20) rồi [20, 30)) là hợp lệ vì end không tính; khoảng nằm gọn bên trong một khoảng đã có.

Bài tập

Bài 1: Phần tử nhỏ thứ K trong BST (tương tự LeetCode 230)

Đề: cho gốc một BST và số k, trả về giá trị nhỏ thứ k (đếm từ 1).

Lời giải Bài 1

Inorder của BST là dãy tăng, nên phần tử thứ k khi duyệt inorder là đáp án. Dùng bản lặp để dừng sớm, không cần duyệt hết cây.

import java.util.*;

public class Main {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static int kthSmallestBST(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) { stack.push(cur); cur = cur.left; }
            cur = stack.pop();
            if (--k == 0) return cur.val;      // stop early, no need to visit the rest
            cur = cur.right;
        }
        throw new IllegalArgumentException("k is larger than the tree size");
    }

    //        4
    //      2   6
    //     1 3 5 7
    static TreeNode sample() {
        return new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                               new TreeNode(6, new TreeNode(5), new TreeNode(7)));
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check(1, kthSmallestBST(sample(), 1));
        check(5, kthSmallestBST(sample(), 5));
        check(7, kthSmallestBST(sample(), 7));
    }
}

Độ phức tạp O(h + k). Câu hỏi tiếp hay gặp: “cây bị sửa liên tục và hỏi k liên tục thì sao?” Lưu thêm kích thước cây con ở mỗi nút (order-statistic tree), khi đó mỗi lần hỏi O(h).

Bài 2: Đập đá (tương tự LeetCode 1046)

Đề: mỗi lượt lấy hai viên nặng nhất y ≥ x đập vào nhau: bằng nhau thì cả hai vỡ, khác thì còn lại một viên nặng y - x. Trả về khối lượng viên cuối cùng, hoặc 0 nếu không còn viên nào.

Lời giải Bài 2

“Lặp lại việc lấy hai phần tử lớn nhất” là tín hiệu max-heap.

import java.util.*;

public class Main {
    static int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) maxHeap.offer(s);
        while (maxHeap.size() > 1) {
            int y = maxHeap.poll(), x = maxHeap.poll();
            if (y != x) maxHeap.offer(y - x);
        }
        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }

    static void check(Object expected, Object actual) {
        String e = String.valueOf(expected), a = String.valueOf(actual);
        System.out.println((e.equals(a) ? "OK    " : "FAIL  ") + "expected " + e + ", got " + a);
    }

    public static void main(String[] args) {
        check(1, lastStoneWeight(new int[]{2, 7, 4, 1, 8, 1}));
        check(0, lastStoneWeight(new int[]{3, 3}));
        check(5, lastStoneWeight(new int[]{5}));
    }
}

O(n log n) thời gian, O(n) bộ nhớ. Edge case: một viên duy nhất; hai viên bằng nhau.

Cách mình chạy thử tất cả lời giải

Mọi lời giải trong bài nằm trong một file TreesHeaps.java kèm hàm main tự kiểm tra, chạy bằng java TreesHeaps.java (JDK 21, chạy file nguồn trực tiếp, không cần biên dịch riêng). Kết quả: passed=52 failed=0.

Các test chính, trên cây BST đầy đủ 4 / 2 6 / 1 3 5 7 và một cây lệch 1 → 2 → 3:

  • Duyệt: inorder ra 1..7, preorder ra 4, 2, 1, 3, 6, 5, 7, cây rỗng ra danh sách rỗng.
  • Level order: [[4], [2, 6], [1, 3, 5, 7]]; cây lệch ra ba tầng một phần tử.
  • Đường kính: 4 với cây đầy đủ, 0 với cây một nút, 4 với một cây mà đường dài nhất không qua gốc.
  • BST: cây đúng, cây rỗng, cây sai ở cháu (bẫy ở trên), giá trị trùng, nút mang Integer.MAX_VALUE và MIN_VALUE.
  • LCA: hai lá cùng cha, hai lá khác phía gốc, một nút là tổ tiên của nút kia; bản BST cho (5, 7) → 6, (1, 7) → 4, (2, 3) → 2.
  • Heap: kthLargest([3,2,1,5,6,4], 2) = 5, có trùng, k = n; top-K [1,1,1,2,2,3], k = 2 → [1, 2]; gộp K danh sách với mảng rỗng, toàn null, một danh sách.
  • Median: các bước 1 → 1.5 → 2, hai số Integer.MAX_VALUE (kiểm tràn số), 2.000 số ngẫu nhiên so với sort.
  • Lịch: chồng giờ, chạm mép, nằm gọn bên trong.

Ghi nhớ

  • Viết được khuôn “hỏi hai con rồi gộp” và áp vào chiều cao, đường kính, LCA.
  • Viết được inorder bằng stack và level order bằng queue.
  • Giải thích được vì sao kiểm tra BST phải truyền khoảng (low, high).
  • Biết vì sao top-K lớn nhất dùng min-heap kích thước K, và độ phức tạp O(n log K).
  • Biết khi nào chọn TreeMap thay vì PriorityQueue.

Câu hỏi phỏng vấn

Junior

DFS và BFS trên cây khác nhau thế nào, mỗi cái dùng cấu trúc gì?

DFS đi sâu một nhánh tới lá rồi mới quay lại, dùng stack (hoặc chính call stack khi đệ quy); BFS đi hết từng tầng, dùng queue.

  • DFS tốn bộ nhớ O(chiều cao), hợp với bài tính từ dưới lên như chiều cao, đường kính, đường đi gốc tới lá.
  • BFS tốn bộ nhớ O(độ rộng), hợp với bài theo tầng hoặc “nút gần gốc nhất”: BFS gặp nó trước tiên.
PriorityQueue của Java là min-heap hay max-heap?

Mặc định là min-heap theo thứ tự tự nhiên: poll() trả phần tử nhỏ nhất.

Muốn max-heap thì truyền Comparator.reverseOrder() (hoặc Collections.reverseOrder()). Với object, truyền comparator như Comparator.comparingInt(Task::priority). PriorityQueue không thread-safe; đa luồng dùng PriorityBlockingQueue.

Mid

Vì sao duyệt inorder của BST ra dãy tăng, và dùng điều đó vào việc gì?

Vì inorder thăm hết cây con trái (toàn số nhỏ hơn), rồi nút, rồi cây con phải (toàn số lớn hơn), lặp lại ở mọi tầng.

Ứng dụng: kiểm tra BST (dãy phải tăng ngặt), tìm phần tử nhỏ thứ k (dừng ở bước thứ k), duyệt khoảng giá trị, gộp hai BST bằng cách gộp hai dãy tăng.

Tìm 100 số lớn nhất trong 10 triệu số. Bạn làm thế nào và tốn bao nhiêu?

Duyệt một lần với min-heap kích thước 100: O(n log K), tức cỡ 10⁷ × log₂100 ≈ 7·10⁷ phép so sánh, bộ nhớ chỉ 100 phần tử.

Sort toàn bộ là O(n log n) và phải giữ 10 triệu số trong RAM. Nếu dữ liệu là luồng (đọc từ file, Kafka) thì heap là lựa chọn tự nhiên vì không cần biết trước n. Nếu dữ liệu đã nằm trong database thì để ORDER BY ... LIMIT 100 trên index làm.

Gộp K danh sách đã sắp xếp: so sánh dùng heap với gộp lần lượt.

Heap cho O(N log k); gộp lần lượt từng danh sách vào kết quả là O(N·k) vì phần đã gộp bị duyệt lại k lần.

Gộp từng cặp (chia đôi như merge sort) cũng đạt O(N log k) và không cần heap. Trong thực tế, đây là bước gộp của external sort và của các engine lưu trữ kiểu LSM khi gộp nhiều file đã sắp xếp.

Senior

Thiết kế median của luồng số. Nếu dữ liệu quá lớn cho RAM thì sao?

Hai heap: max-heap cho nửa nhỏ, min-heap cho nửa lớn, lệch nhau tối đa một phần tử. Thêm O(log n), đọc median O(1).

Khi không giữ được hết dữ liệu:

  • Giá trị nằm trong miền nhỏ (ví dụ độ trễ 0 tới 10.000 ms): đếm theo bucket, median là bucket chứa phần tử thứ n/2, O(1) bộ nhớ theo n.
  • Chấp nhận gần đúng: sketch như t-digest hoặc HDRHistogram cho p50, p99 với sai số có kiểm soát, gộp được giữa nhiều máy.
  • Cửa sổ trượt: hai heap không xoá phần tử bất kỳ nhanh được, đổi sang hai TreeMap đếm số lần xuất hiện.
Khi nào bạn dùng TreeMap thay vì HashMap rồi sort, và cái giá là gì?

Khi tập dữ liệu thay đổi liên tục và cần truy vấn theo thứ tự (lân cận, khoảng, nhỏ nhất, lớn nhất) xen giữa các lần thay đổi.

  • HashMap rồi sort mỗi lần hỏi là O(n log n) cho mỗi truy vấn; TreeMap giữ thứ tự sẵn, mỗi thao tác O(log n).
  • Cái giá: get/put O(log n) thay vì O(1) trung bình, mỗi entry là một nút cây đỏ đen (thêm con trỏ, màu), cache kém hơn.
  • Chỉ sort một lần cuối (ví dụ báo cáo) thì HashMap rồi sort rẻ hơn.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
traversal /trəˈvɝː.səl/ phép duyệt “An inorder traversal of a BST gives the keys in sorted order.”
level order /ˈlev.əl ˈɔːr.dɚ/ duyệt theo tầng “I’d use a queue for a level order traversal.”
skewed tree /skjuːd triː/ cây lệch “On a skewed tree the recursion can overflow the stack.”
binary search tree /ˈbaɪ.nɚ.i sɝːtʃ triː/ cây tìm kiếm nhị phân “A binary search tree gives logarithmic lookups only when it’s balanced.”
lowest common ancestor /ˈloʊ.ɪst ˈkɑː.mən ˈæn.ses.tɚ/ tổ tiên chung gần nhất “The lowest common ancestor is where the two paths split.”
heap /hiːp/ đống, cây heap “A heap gives me the minimum in constant time.”
priority queue /praɪˈɔːr.ə.ti kjuː/ hàng đợi ưu tiên “Java’s priority queue is a min-heap by default.”
top-K /tɑːp keɪ/ K phần tử đầu “For top-K I keep a min-heap of size K.”
red-black tree /red blæk triː/ cây đỏ đen “TreeMap is a red-black tree, so every operation is O(log n).”

Ghi chép tự tổng hợp từ tài liệu chính thức và kinh nghiệm thực tế.