fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3.  
  4. using namespace std;
  5.  
  6. struct TreeNode {
  7.     int val;
  8.     TreeNode *left;
  9.     TreeNode *right;
  10.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  11. };
  12.  
  13. int countIslands(TreeNode* node, unordered_map<TreeNode*, int>& dp) {
  14.     if (node == nullptr) {
  15.         return 0;
  16.     }
  17.     int leftIslands = countIslands(node->left, dp);
  18.     int rightIslands = countIslands(node->right, dp);
  19.     if (node->val == 0) {
  20.         dp[node] = leftIslands + rightIslands;
  21.     } else {
  22.         if (node->left != nullptr && node->left->val == 1 && node->right != nullptr && node->right->val == 1) {
  23.             dp[node] = leftIslands + rightIslands - 1; // Merging two islands
  24.         } else if (node->left != nullptr && node->left->val == 1) {
  25.             dp[node] = leftIslands + rightIslands; // Only left child is 1
  26.         } else if (node->right != nullptr && node->right->val == 1) {
  27.             dp[node] = leftIslands + rightIslands; // Only right child is 1
  28.         } else {
  29.             dp[node] = 1 + leftIslands + rightIslands;
  30.         }
  31.     }
  32.  
  33.     return dp[node];
  34. }
  35.  
  36. int findIslands(TreeNode* root) {
  37.     unordered_map<TreeNode*, int> dp;
  38.     return countIslands(root, dp);
  39. }
  40.  
  41. int main() {
  42.     TreeNode* root = new TreeNode(0);
  43.     root->left = new TreeNode(1);
  44.     root->right = new TreeNode(1);
  45.  
  46.     root->left->left = new TreeNode(0);
  47.     root->left->right = new TreeNode(1);
  48.  
  49.     root->left->left->left = new TreeNode(1);
  50.     root->left->left->right = new TreeNode(1);
  51.  
  52.     root->right->left = new TreeNode(1);
  53.     root->right->right = new TreeNode(0);
  54.  
  55.     cout << "Number of islands: " << findIslands(root) << endl;
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Number of islands: 4
https://ideone.com/CglP1U
language:
C++14 (gcc 8.3)
created:
9 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!