fork download
copy 
  1. // In a tree of zeroes and ones , give the final answer as no.of islands can be formed .
  2. // It forms an island where ones are connected and surrounded by zeroes .
  3. // Bottom Up DFS (POSTORDER TRAVERSAL) : DP on Tree
  4. // input will be only root of tree
  5. // dp[i] is subtree rooted at node i will give no. of islands in subtree rooted at i
  6.  
  7. #include <iostream>
  8. #include <unordered_map>
  9. using namespace std;
  10.  
  11. class Node
  12. {
  13. public:
  14.     Node *right;
  15.     Node *left;
  16.     int data;
  17.     Node()
  18.     {
  19.         right = nullptr;
  20.         left = nullptr;
  21.     }
  22.     Node(int val)
  23.     {
  24.         right = nullptr;
  25.         left = nullptr;
  26.         data = val;
  27.     }
  28. };
  29.  
  30. int getAns(Node *root, unordered_map<Node *, int> dp)
  31. {
  32.     if (root == nullptr)
  33.     {
  34.         return 0;
  35.     }
  36.  
  37.     if (!root->left && !root->right)
  38.     {
  39.         dp[root] = root->data;
  40.         return dp[root];
  41.     }
  42.  
  43.     int leftTreeIslands = getAns(root->left, dp);
  44.     int rightTreeIslands = getAns(root->right, dp);
  45.  
  46.     if (root->data == 0)
  47.     {
  48.         dp[root] = leftTreeIslands + rightTreeIslands;
  49.     }
  50.     else
  51.     {
  52.         if ((root->right && root->right->data) && (root->left && root->left->data))
  53.         {
  54.             dp[root] = leftTreeIslands + rightTreeIslands - 1;
  55.         }
  56.         else if ((root->right && root->right->data) && (root->left && root->left->data))
  57.         {
  58.             dp[root] = leftTreeIslands + rightTreeIslands;
  59.         }
  60.         else
  61.         {
  62.             dp[root] = leftTreeIslands + rightTreeIslands + 1;
  63.         }
  64.     }
  65.  
  66.     return dp[root];
  67. }
  68.  
  69. Node *createTree()
  70. {
  71.     Node *root = new Node(0);
  72.     Node *l1 = new Node(1);
  73.     root->left = l1;
  74.     Node *r1 = new Node(0);
  75.     root->right = r1;
  76.     Node *l2 = new Node(1);
  77.     l1->left = l2;
  78.     Node *r2 = new Node(0);
  79.     l2->right = r2;
  80.     Node *r3 = new Node(1);
  81.     r1->right = r3;
  82.     return root;
  83. }
  84.  
  85. int main()
  86. {
  87.     unordered_map<Node *, int> dp;
  88.     Node *root = createTree();
  89.     int ans = getAns(root, dp);
  90.     cout << ans << endl;
  91.     return 0;
  92. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/braAPT
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!