Skip to content

Commit 132a86f

Browse files
daiwbdaiwb
committed
LeetCode 5/19/2014
1 parent 7262255 commit 132a86f

File tree

3 files changed

+216
-0
lines changed

3 files changed

+216
-0
lines changed

‎LeetCode/buildTree.cpp‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
struct TreeNode {
31+
int val;
32+
TreeNode *left;
33+
TreeNode *right;
34+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
35+
};
36+
37+
class Solution {
38+
public:
39+
TreeNode *doit(vector<int> &preorder, vector<int> &inorder, int st1, int ed1, int st2, int ed2) {
40+
int n = ed1 - st1 + 1;
41+
if (n == 0) return NULL;
42+
43+
int idx = -1;
44+
FOR(i,st2,ed2) {
45+
if (inorder[i] == preorder[st1]) {
46+
idx = i;
47+
break;
48+
}
49+
}
50+
51+
int num = idx - st2;
52+
53+
TreeNode *root = new TreeNode(preorder[st1]);
54+
root->left = doit(preorder, inorder, st1 + 1, st1 + num, st2, idx - 1);
55+
root->right = doit(preorder, inorder, st1 + num + 1, ed1, idx + 1, ed2);
56+
return root;
57+
}
58+
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
59+
int n = preorder.size();
60+
if (n == 0) return NULL;
61+
return doit(preorder, inorder, 0, n - 1, 0, n - 1);
62+
}
63+
};
64+
65+
int main() {
66+
VI p, q;
67+
int a[] = {1,2,4,3,5,6};
68+
int b[] = {4,2,1,5,3,6};
69+
REP(i,6) {
70+
p.PB(a[i]);
71+
q.PB(b[i]);
72+
}
73+
Solution s;
74+
TreeNode *res = s.buildTree(p, q);
75+
return 0;
76+
}

‎LeetCode/buildTree2.cpp‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
struct TreeNode {
31+
int val;
32+
TreeNode *left;
33+
TreeNode *right;
34+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
35+
};
36+
37+
class Solution {
38+
public:
39+
TreeNode *doit(vector<int> &inorder, vector<int> &postorder, int st1, int ed1, int st2, int ed2) {
40+
int n = ed1 - st1 + 1;
41+
if (n == 0) return NULL;
42+
43+
int idx = -1;
44+
FOR(i,st1,ed1) {
45+
if (inorder[i] == postorder[ed2]) {
46+
idx = i;
47+
break;
48+
}
49+
}
50+
51+
int num = idx - st1;
52+
53+
TreeNode *root = new TreeNode(postorder[ed2]);
54+
root->left = doit(inorder, postorder, st1, idx - 1, st2, st2 + num - 1);
55+
root->right = doit(inorder, postorder, idx + 1, ed1, st2 + num, ed2 - 1);
56+
return root;
57+
}
58+
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
59+
int n = inorder.size();
60+
if (n == 0) return NULL;
61+
return doit(inorder, postorder, 0, n - 1, 0, n - 1);
62+
}
63+
};
64+
65+
int main() {
66+
VI p, q;
67+
int a[] = {4,2,1,5,3,6};
68+
int b[] = {4,2,5,6,3,1};
69+
REP(i,6) {
70+
p.PB(a[i]);
71+
q.PB(b[i]);
72+
}
73+
Solution s;
74+
TreeNode *res = s.buildTree(p, q);
75+
return 0;
76+
}

‎LeetCode/zigzagLevelOrder.cpp‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
struct TreeNode {
31+
int val;
32+
TreeNode *left;
33+
TreeNode *right;
34+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
35+
};
36+
37+
class Solution {
38+
public:
39+
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
40+
vector<VI> res;
41+
if (root == NULL) return res;
42+
deque<TreeNode *> que;
43+
que.PB(root);
44+
bool flag = true;
45+
while (!que.empty()) {
46+
flag = !flag;
47+
VI tmp;
48+
int n = que.size();
49+
REP(i,n) {
50+
tmp.PB(que[i]->val);
51+
if (que[i]->left != NULL) que.PB(que[i]->left);
52+
if (que[i]->right != NULL) que.PB(que[i]->right);
53+
}
54+
if (flag) reverse(tmp.begin(), tmp.end());
55+
res.PB(tmp);
56+
REP(i,n) que.pop_front();
57+
}
58+
return res;
59+
}
60+
};
61+
62+
int main() {
63+
return 0;
64+
}

0 commit comments

Comments
 (0)