Đếm số cây con giá trị đơn nhất (Uni-value Subtrees) trong C++

Cho một cây nhị phân, nhiệm vụ là đếm số lượng cây con giá trị đơn nhất (uni-value subtrees). Một cây con được gọi là giá trị đơn nhất khi tất cả các nút trong cây con đó có cùng một giá trị.

Ví dụ minh họa

Đầu vào: root = [5,1,5,5,5,null,5]

Đầu ra: 4

Thuật toán giải quyết

Ta sử dụng phương pháp đệ quy (DFS) pós-order (hậu tự) để kiểm tra từng cây con:

1. Định nghĩa hàm solve(node) trả về true nếu cây con gốc tại node là uni-value.
2. Nếu node là null, trả về true (cây rỗng mặc định thỏa mãn).
3. Gọi đệ quy cho nút con trái (left) và nút con phải (right).
4. Nếu bất kỳ cây con trái hoặc phải nào không phải uni-value, trả về false.
5. Nếu nút con trái tồn tại và giá trị của nó khác giá trị nút hiện tại, trả về false.
6. Nếu nút con phải tồn tại và giá trị của nó khác giá trị nút hiện tại, trả về false.
7. Nếu vượt qua các kiểm tra trên, tăng biến đếm ret lên 1 và trả về true.
8. Từ hàm chính, khởi tạo ret = 0, gọi solve(root) và trả về ret.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

class Solution {
public:
    int ret = 0;
    bool solve(TreeNode* node) {
        if (!node) return true;
        bool left = solve(node->left);
        bool right = solve(node->right);
        if (!left || !right) return false;
        if (node->left && node->val != node->left->val) return false;
        if (node->right && node->val != node->right->val) return false;
        ret++;
        return true;
    }
    int countUnivalSubtrees(TreeNode* root) {
        ret = 0;
        solve(root);
        return ret;
    }
};

Độ phức tạp

• Thời gian: O(n) - duyệt qua từng nút đúng một lần.
• Không gian: O(h) - độ sâu đệ quy tối đa bằng chiều cao cây (h), trong trường hợp xấu nhất O(n).

Kết quả kiểm thử

Đầu vào: {5,1,5,5,5,NULL,5}
Đầu ra: 4