Count Good Nodes: giá trị lớn nhất trên đường đi nói gì khi bạn đi xuống cây

Định nghĩa của good node khá gọn: không có ancestor nào trên đường từ root đến node đó có giá trị lớn hơn giá trị của node hiện tại. Root luôn thỏa mãn — nó không có ancestor nào cả. Cái bẫy nằm ở từ "đường đi". Nếu đọc định nghĩa theo nghĩa đen, bạn sẽ kéo theo toàn bộ lịch sử path xuống cây và kiểm tra nó tại từng node. Đó là cách brute force, và nó chậm vì một lý do mà constraints nói rất rõ.

Cây trên là Example 1: root = [3,1,4,3,null,1,5]. Bốn node là good: root (3), con phải (4), con phải-phải (5), và con trái-trái (3). Toàn bộ những gì giải pháp tối ưu làm đều xuất phát từ một nhận thức: bạn chỉ cần một con số duy nhất — giá trị lớn nhất đã thấy trên đường đi — chứ không cần danh sách đầy đủ các ancestor.

Đề bài

Cho một binary tree, đếm số node "good" — một node X là good nếu trên đường đi từ root đến X không có node nào có giá trị lớn hơn nghiêm ngặt giá trị của X. Root luôn thỏa mãn. Đề gốc: LeetCode 1448.

Ràng buộc:
- Số lượng node trong binary tree thuộc khoảng [1, 10^5].
- Giá trị mỗi node nằm trong [-10^4, 10^4].

Constraints nói gì trước khi bạn viết một dòng code

Số lượng node nằm trong khoảng [1, 10^5]. Điều này ngay lập tức loại trừ O(n²). Một giải pháp quét path kiểm tra O(depth) ancestor cho mỗi node. Trên cây cân bằng, depth là O(log n), cho tổng O(n log n). Nhưng với chuỗi lệch hoàn toàn gồm 10^5 node, depth chạm O(n), biến giải pháp thành O(n²) — khoảng 10^10 phép tính. Bạn sẽ time out cách xa.

Giá trị node nằm trong [-10^4, 10^4]. Hai điều rút ra từ đây. Thứ nhất, giá trị khởi tạo "max đã thấy" phải nhỏ hơn mọi giá trị trong cây — float('-inf') trong Python hoặc int.MinValue trong C# hoạt động đúng kể cả với giá trị âm. Nếu bạn khởi tạo bằng 0, một cây như [-1, -2, -3] sẽ phân loại sai mọi node. Thứ hai, 0 không thể là sentinel cho bất cứ điều gì cấu trúc.

Dải giá trị đủ hẹp để bạn không cần lo về integer overflow khi lưu running maximum. int.MinValue ở lần gọi đầu tiên là ranh giới duy nhất cần xử lý, và giá trị được chặn tại 10^4.

Approach 1: kéo theo toàn bộ path (brute force)

Cách đọc đề bài trực tiếp nhất: duy trì một list tất cả các giá trị trên path từ root đến node hiện tại. Để kiểm tra một node, quét list tìm giá trị nào lớn hơn giá trị của node đó. Backtrack (pop khỏi path) khi rời node.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, path):
            if not node:
                return 0
 
            path.append(node.val)
 
            is_good = True
            for val in path[:-1]:  # không bao gồm chính node hiện tại
                if val > node.val:
                    is_good = False
                    break
 
            count = 1 if is_good else 0
            count += dfs(node.left, path)
            count += dfs(node.right, path)
 
            path.pop()  # backtrack
            return count
 
        return dfs(root, [])

public class Solution {
    public int GoodNodes(TreeNode root) {
        return DFS(root, new List<int>());
    }
 
    private int DFS(TreeNode node, List<int> path) {
        if (node == null) return 0;
 
        path.Add(node.val);
 
        bool isGood = true;
        for (int i = 0; i < path.Count - 1; i++) {
            if (path[i] > node.val) {
                isGood = false;
                break;
            }
        }
 
        int count = isGood ? 1 : 0;
        count += DFS(node.left, path);
        count += DFS(node.right, path);
 
        path.RemoveAt(path.Count - 1);  // backtrack
        return count;
    }
}

Tại mỗi node, bạn quét tối đa O(depth) giá trị đã có. Tổng cộng trên tất cả các node, thời gian là O(n * depth) — O(n log n) trung bình trên cây cân bằng, O(n²) worst case trên chuỗi lệch. Space là O(h) cho cả call stack lẫn path list. Đây là cách tiếp cận bạn hầu như không muốn dùng với n = 10^5.

Insight thu gọn việc quét path xuống O(1) mỗi node

Việc quét là thừa. Khi bạn đến một node, bạn không cần xem lại từng ancestor. Bạn chỉ quan tâm đến giá trị lớn nhất trong số chúng. Và quan trọng hơn, bạn đã có giá trị đó rồi — bạn đã tính nó trong lúc đi từ root xuống. Thay vì giữ toàn bộ list và quét nó, hãy giữ một con số: giá trị lớn nhất đã thấy trên path từ root đến parent của node hiện tại.

Một node là good khi và chỉ khi node.val >= max_so_far. Sau khi kiểm tra, cập nhật max_so_far = max(max_so_far, node.val) trước khi đi sâu hơn. Giá trị cập nhật này trở thành constraint cho mọi node trong subtree bên dưới. Đây là top-down parameter passing: bạn đẩy state từ cha xuống con thay vì đọc lại từ một cấu trúc được lưu trữ.

Approach 2: DFS với running maximum

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_so_far):
            if not node:
                return 0
 
            count = 1 if node.val >= max_so_far else 0
            new_max = max(max_so_far, node.val)
 
            count += dfs(node.left, new_max)
            count += dfs(node.right, new_max)
            return count
 
        return dfs(root, float('-inf'))

public class Solution {
    public int GoodNodes(TreeNode root) {
        return DFS(root, int.MinValue);
    }
 
    private int DFS(TreeNode node, int maxSoFar) {
        if (node == null) return 0;
 
        int count = node.val >= maxSoFar ? 1 : 0;
        int newMax = Math.Max(maxSoFar, node.val);
 
        count += DFS(node.left, newMax);
        count += DFS(node.right, newMax);
        return count;
    }
}

Mỗi node được thăm đúng một lần. Tại mỗi node, công việc là O(1): một phép so sánh, một lần tính max, hai lần gọi đệ quy. Time là O(n). Space là O(h) cho call stack — O(log n) trên cây cân bằng, O(n) trên chuỗi lệch. Không cần data structure phụ nào ngoài các call frame.

Trace tay qua Example 1: root = [3,1,4,3,null,1,5]

Lời gọi đầu tiên: dfs(node=3, max_so_far=-inf)

Bước 1: node=3,  max_so_far=-inf  ->  3 >= -inf, count=1,  new_max=3
  Bước 2: node=1,  max_so_far=3   ->  1 < 3,     count=0,  new_max=3
    Bước 3: node=3,  max_so_far=3 ->  3 >= 3,    count=1,  new_max=3
              node.left=null -> 0
              node.right=null -> 0
              trả về 1
    node.right=null -> 0
    trả về 0 + 1 + 0 = 1
  Bước 4: node=4,  max_so_far=3   ->  4 >= 3,    count=1,  new_max=4
    Bước 5: node=1,  max_so_far=4 ->  1 < 4,     count=0,  new_max=4
              node.left=null -> 0, node.right=null -> 0
              trả về 0
    Bước 6: node=5,  max_so_far=4 ->  5 >= 4,    count=1,  new_max=5
              node.left=null -> 0, node.right=null -> 0
              trả về 1
    trả về 1 + 0 + 1 = 2
  trả về 1 + 2 = 3
trả về 1 + 1 + 3 = 4

Bốn good node. Trace này cũng cho thấy tại sao node 1 (con trái của root) không phải good node — khi bạn đến nó, path maximum đã là 3, lớn hơn giá trị của nó.

Tại sao >= chứ không phải >

Điều kiện là node.val >= max_so_far, không phải lớn hơn nghiêm ngặt. Bài toán nói một good node là node không có ancestor nào có giá trị lớn hơn nghiêm ngặt giá trị của nó. Bằng nhau là được — node có giá trị bằng đúng path maximum vẫn là good. Viết nhầm > thay vì >= gây ra đúng một loại lỗi: các node có giá trị bằng maximum hiện tại bị đếm sai là bad.

Các edge case đáng gọi tên

Một node duy nhất (root = [1]): DFS gọi dfs(node=1, max_so_far=-inf). Điều kiện 1 >= -inf là đúng. Cả hai con là null và trả về 0. Kết quả là 1. Đúng — root luôn là good node.

Tất cả giá trị bằng nhau (ví dụ [5,5,5,5,5]): mọi node từ level thứ hai trở đi đều có node.val == max_so_far. Tất cả đều là good. Điều kiện >= xử lý đúng điều này; > chỉ đếm được root.

Giảm dần nghiêm ngặt từ trên xuống (ví dụ [5,4,3]): chỉ root là good. Mỗi con thấy max_so_far bằng giá trị cha, lớn hơn giá trị của con. Kết quả là 1 bất kể kích thước cây.

Toàn giá trị âm (ví dụ [-3,-4,-1]): nếu bạn khởi tạo max_so_far bằng 0 thay vì -inf, root (giá trị -3) sẽ thất bại điều kiện (-3 >= 0) và toàn bộ cây trả về 0 good node — sai. Khởi tạo bằng float('-inf') hoặc int.MinValue đảm bảo root luôn qua, như bài toán đảm bảo.

Chuỗi lệch phải gồm 10^5 node, tất cả giá trị bằng nhau: mọi node đều là good. Với Approach 1, đây là worst case cho cả time (O(n²) path scan) lẫn space (O(n) path list và call stack cộng lại). Với Approach 2, bạn trả O(n) time và O(n) call stack — vẫn là worst case cho space trên cây lệch, nhưng không thể tránh vì bạn phải thăm mọi node.

Bảng so sánh

Sự khác biệt về space nhỏ hơn về time — cả hai approach đều dùng O(h) cho call stack, và Approach 1 thêm O(h) nữa cho path list. Trên cây cân bằng, phần thêm đó là O(log n), không đáng kể. Chi phí thực sự nằm ở time: O(n²) so với O(n) tại n = 10^5 là ranh giới giữa chạy được và time out.

Cách tôi tiếp cận trong phỏng vấn hay production

Approach 2 ngay lập tức. Không phải vì Approach 1 sai, mà vì insight quá sạch để bỏ qua: bạn không cần toàn bộ path, bạn chỉ cần tóm tắt scalar của path. Khi nhận ra điều đó, phần còn lại xuất hiện trong bốn dòng. Approach 1 đáng đề cập như điểm xuất phát dịch-trực-tiếp, cụ thể là để tạo động lực cho optimization — nhưng tôi sẽ không code đầy đủ; tôi sẽ nói "mang theo path là O(n²), thứ chúng ta thực sự cần là running maximum" rồi đi thẳng sang Approach 2.

Pattern ở đây là top-down parameter passing: thay vì đọc accumulator từ cấu trúc lưu trữ, bạn đẩy state như một tham số từ cha xuống con. Cách này tránh hoàn toàn nhu cầu dùng data structure bên ngoài và giữ cho hàm tự khép kín. Cơ chế chính xác này xuất hiện trong hàng chục bài toán cây.

Vị trí trong series trees và những gì tiếp theo

Đây là bài thứ 12 trong series. Đến đây bạn đã thấy DFS trên một cây (maximum depth, invert, same tree), BFS level-order traversal, BST validation, và subtree matching. Count Good Nodes là bài đầu tiên trong series yêu cầu bạn mang thông tin đi nghiêm ngặt từ trên xuống — từ ancestor xuống descendant — thay vì tích lũy kết quả từ lá lên (như trong max depth) hay không truyền state bổ sung nào cả (như trong invert).

Pattern cơ bản là "path information được truyền top-down qua DFS parameters." Nó xuất hiện trong:

Path Sum (112): có path nào từ root đến leaf có tổng các giá trị bằng target không? Cùng cấu trúc — mang running sum như tham số, kiểm tra tại leaf. Sự khác biệt là bạn tính tổng thay vì lấy max, và kiểm tra chỉ tại leaf.

Path Sum II (113): thu thập tất cả các path như vậy. Thêm backtracking vào path list — đưa bạn trở lại mechanics giống Approach 1, nhưng lần này path list là output, không phải thứ trung gian bạn có thể tối ưu đi.

Binary Tree Maximum Path Sum (124): escalation khó nhất. Một "path" không còn phải bắt đầu từ root, nên trick truyền tham số top-down không áp dụng trực tiếp. Bạn cần bottom-up DFS trả về lợi nhuận single-branch tốt nhất từ mỗi node và theo dõi global maximum qua tất cả các path.

Longest Univalue Path (687): mang một invariant khác — độ dài của chuỗi giá trị giống nhau hiện tại kết thúc tại parent. Cho thấy top-down parameter passing hoạt động với bất kỳ scalar invariant nào, không chỉ max hay sum.

Mental model để mang theo: khi một bài toán cây yêu cầu kiểm tra điều kiện phụ thuộc vào path từ root đến node hiện tại, hãy nghĩ "scalar tối thiểu (hoặc struct nhỏ) nào tôi có thể truyền từ cha xuống con nắm bắt được mọi thứ liên quan về path đó?" Với bài này, câu trả lời là giá trị lớn nhất đã thấy. Làm chủ bước thu gọn đó là điều khiến một bài O(n²) trở nên hiển nhiên để giải trong O(n).