GeeksForGeeks-Problem/5 May Vertical sum at 0a85bba584237745cec4615f60f9fd1324c76b2e · Michael-Calce/GeeksForGeeks-Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution{

  public:

    int Nodes(Node* root){

        if(root == NULL) return 0;

        return 1 + (Nodes(root->left) + Nodes(root->right));

    }

    void fill(Node* root , vector<int>& temp , int idx , int n){

        //if(idx == -1 || idx >= n ) return;

        if(root == NULL) return;

        temp[idx] += root->data;

        fill(root->left,temp,idx-1,n);

        fill(root->right,temp,idx+1,n);

    }

    vector <int> verticalSum(Node *root) {

        // add code here.

        int n = Nodes(root);

        vector<int> temp(1e5,0);

        int idx = 50000;

        fill(root,temp,idx,n);

        vector<int> result;

        bool flag = false;

        for(int i = 0 ; i < 1e5 ; i++){

            //cout<<temp[i]<<" ";

            if(temp[i] == 0 && flag == true) break;

            if(temp[i] == 0) continue;

            result.push_back(temp[i]);

            flag = true;

        }

        return result;

    }

};