Tổng số nút có ông bà chẵn có giá trị trong C ++

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm tổng các giá trị của các nút có giá trị là họ chẵn. (Ông nội của một nút là nút cha của nút cha, nếu nó tồn tại.). Nếu không có nút nào như vậy với một ông bà có giá trị chẵn, thì trả về 0. Vì vậy, nếu cây giống như -

Kết quả đầu ra sẽ là 18. Các nút màu đỏ là các nút có giá trị ông bà chẵn, trong khi các nút màu xanh lam là các nút ông bà có giá trị chẵn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là mẹ
• Xác định một phương thức có tên là giải quyết (), phương thức này sẽ sử dụng nút và điểm
• nếu nút là null, thì trả về
• nếu par không phải là null và par có trong cha và cha [par] không phải là 0 và giá trị của cha [par] là chẵn, thì
  • res:=res + giá trị của nút
• cha [node]:=par
• giải quyết (bên trái của nút, nút)
• giải quyết (bên phải của nút, nút)
• Từ phương thức chính, đặt res:=0, gọi giải quyết (root, Null), sau đó trả về res

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
   }
};
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));
}

Đầu vào

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

Đầu ra

18