ผลรวมของโหนดที่มีคู่บิดาค่าคู่ใน C++

สมมติว่าเรามีต้นไม้แบบทวิภาค (binary tree) เราต้องการหาผลรวมของค่าโหนดที่มีคู่บิดา (grandparent) เป็นค่าคู่ คู่บิดาของโหนดคือ พ่อของพ่อของโหนดนั้น (ถ้ามีอยู่) หากไม่มีโหนดใดที่มีคู่บิดาค่าคู่ ให้คืนค่า 0

ตัวอย่างเช่น ต้นไม้ดังภาพ:

ผลลัพธ์จะเป็น 18 โหนดสีแดงคือโหนดที่มีคู่บิดาค่าคู่ ส่วนโหนดสีน้ำเงินคือคู่บิดาที่มีค่าคู่

ขั้นตอนการแก้ปัญหา

• กำหนดแผนที่ (map) ชื่อ parent เพื่อเก็บข้อมูลพ่อของแต่ละโหนด
• กำหนดเมธอด solve() รับพารามิเตอร์ node และ par (พ่อของโหนดปัจจุบัน)
• ถ้า node เป็น null ให้คืนค่า
• ถ้า par ไม่ใช่ null และมีอยู่ใน parent และ parent[par] ไม่ใช่ 0 และค่าของ parent[par] เป็นเลขคู่ แล้ว:
  • res := res + ค่าของ node
• parent[node] := par
• เรียก solve(left of node, node)
• เรียก solve(right of node, node)
• จากเมธอดหลัก กำหนด res := 0 เรียก solve(root, Null) แล้วคืนค่า res

ตัวอย่างโค้ด (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));
}

อินพุต

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

เอาต์พุต

18