Tổng các nút có tổ tiên giá trị chẵn trong C++

Cho một cây nhị phân, ta cần tìm tổng giá trị của các nút có tổ tiên (grandparent) mang giá trị chẵn. Tổ tiên của một nút là nút cha của nút cha nó (nếu tồn tại). Nếu không có nút nào thỏa mãn, trả về 0.

Ví dụ với cây sau:

Kết quả sẽ là 18. Các nút đỏ là những nút có tổ tiên giá trị chẵn, các nút xanh là tổ tiên có giá trị chẵn.

Giải thuật

1. Định nghĩa một map parent để lưu cha của mỗi nút.
2. Định nghĩa phương thức solve(node, par):
3. Nếu node là null, trả về.
4. Nếu par không null, tồn tại trong parent, và giá trị của parent[par] là chẵn, thì cộng giá trị node vào kết quả.
5. Gán parent[node] = par.
6. Gọi đệ quy solve(node->left, node) và solve(node->right, node).
7. Từ phương thức chính, khởi tạo res = 0, gọi solve(root, NULL), trả về res.

Ví dụ 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;
    }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front(); q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else q.push(temp->right);
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

class Solution {
public:
    int res;
    map <TreeNode*, TreeNode*> parent;
    void solve(TreeNode* node, TreeNode* par = NULL) {
        if(!node) return;
        if(par && parent.count(par) && parent[par] && parent[par]->val % 2 == 0) {
            res += node->val;
        }
        parent[node] = par;
        solve(node->left, node);
        solve(node->right, node);
    }
    int sumEvenGrandparent(TreeNode* root) {
        res = 0;
        parent.clear();
        solve(root);
        return res;
    }
};

int main() {
    vector<int> v = {6,7,8,2,7,1,3,9,NULL,1,4,NULL,NULL,NULL,5};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.sumEvenGrandparent(root));
    return 0;
}

Đầu vào

[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Đầu ra

18