Leetcode75/Leetcode105.cpp at main · kasakvaish/Leetcode75 · 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff                 first
#define ss                 second
#define endl               "\n"
#define ll                 long long
#define ld                 long double
#define loop(a, b, c)      for(ll (a) = (b); (a)<=(c); (a)++)
#define looprev(a, b, c)   for(ll (a) = (b); (a)>=(c); (a)--)
#define pb                 push_back
#define mp                 make_pair
#define pii                pair<ll, ll>
#define vi                 vector<ll>
#define mii                map<ll, ll>
#define pqb                priority_queue<ll>
#define pqs                priority_queue<int, vi, greater<ll> >
#define setbits(x)         __builtin_popcountll(x)
#define zrobits(x)         __builtin_ctzll(x)
#define mod                1000000007
#define inf                1e18
#define ps(x, y)           fixed<<setprecision(y)<<x
#define mk(arr,n,type)     type *arr = new type[n];
#define w(t)               int x; cin>>x; while(x--)
// mt19937                    rng(chrono::steady_clock::now,time_since_epoch(),count());
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void file_i_o(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	/* #ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif */
}


  // Definition for a binary tree node.
/* struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

class Solution {
public:


	TreeNode* buildT(vector<int> &preorder, int preStart, int preEnd, vector<int> &inorder, int inStart, int inEnd, map<int, int> inMap){
		if(preStart > preEnd or inStart > inEnd) return NULL;
		TreeNode* root = new TreeNode(preorder[preStart]);

		int inRoot = inMap[root->val];
		int numLeft = inRoot - inStart;

		root->left = buildT(preorder, preStart+1, preStart+numLeft, inorder, inStart, inRoot-1, inMap);
		root->right = buildT(preorder, preStart+numLeft+1, preEnd, inorder, inRoot+1, inEnd, inMap);

		return root;
	}

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
     	map<int, int> inMap;

     	for(int i = 0; i < inorder.size(); i++){
     		inMap[inorder[i]] = i;
     	}

     	TreeNode* root = buildT(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, inMap);

     	return root;
    }

};
*/


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int startp = 0;

    TreeNode* construct(vector<int>& preorder, vector<int>& inorder, int starti, int endi) {
        if(starti > endi) return NULL;

        TreeNode* root = new TreeNode(preorder[startp++]);
        int k = 0;

        for(int i = starti; i <= endi; i++) {
            if(inorder[i] == root->val) {
                k = i;
                break;
            }
        }
        root->left = construct(preorder, inorder, starti, k-1);
        root->right = construct(preorder, inorder, k+1, endi);

        return root;
    }


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if(n <= 0) return NULL;
        return construct(preorder, inorder, 0, n-1);
    }
};


int main(int argc, char const *argv[])
{

	file_i_o();

	clock_t start, end;
    start = clock();

	w(t){

	/* Write Code Here */


	}

	end = clock();

	double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<"\nTime : "<<fixed<<time_taken<<setprecision(5)<<" s \n";
    cerr<<"\n" << "Coded By S!r Black-D3vil" <<"\n";

	return 0;
}