-
-
Notifications
You must be signed in to change notification settings - Fork 297
/
Copy path106.cpp
128 lines (127 loc) · 4.06 KB
/
106.cpp
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
__________________________________________________________________________________________________
12ms
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
reverse(postorder.begin(),postorder.end());
reverse(inorder.begin(),inorder.end());
int i = 0, j = 0;
if (postorder.size() == 0)
return NULL;
TreeNode * root = new TreeNode(postorder[0]);
vector<TreeNode*> kk;
TreeNode *cur = root;
TreeNode *tem;
kk.push_back(root);
int status = 0;
while (i != postorder.size())
{
if (status == 0)
{
if (postorder[i] != inorder[j])
{
tem = new TreeNode(postorder[i]);
cur->right = tem;
cur = tem;
kk.push_back(cur);
i++;
}
else
{
tem = new TreeNode(postorder[i]);
cur->right = tem;
cur = tem;
j++;
i++;
status = 1;
}
}
else if (status == 1)
{
if (!kk.empty()&&kk.back()->val == inorder[j])
{
cur = kk.back();
j++;
kk.pop_back();
}
else
{
if(postorder[i]!=inorder[j])
{
tem = new TreeNode(postorder[i]);
cur->left = tem;
cur = tem;
kk.push_back(cur);
status = 0;
i++;
}
else
{
tem = new TreeNode(postorder[i]);
cur->left = tem;
cur = tem;
i++;
j++;
}
}
}
}
return root->right;
}
};
__________________________________________________________________________________________________
14136 kb
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty()) {
return nullptr;
} else if (inorder.size() == 1) {
return new TreeNode(inorder[0]);
}
vector<StackElem> stk;
StackElem root(0, 0, inorder.size());
stk.push_back(root);
while (!stk.empty()) {
StackElem elem = stk.back(); stk.pop_back();
elem.node->val = postorder[elem.start2 + elem.length - 1];
int len = 0;
for (; inorder[elem.start1 + len] != elem.node->val; ++len) {}
if (len > 0) {
stk.push_back(StackElem(elem.start1, elem.start2, len));
elem.node->left = stk.back().node;
}
if (elem.length - len - 1 > 0) {
stk.push_back(StackElem(elem.start1 + len + 1, elem.start2 + len, elem.length - len - 1));
elem.node->right = stk.back().node;
}
}
return root.node;
}
private:
struct StackElem {
int start1, start2, length;
TreeNode* node; // To avoid memory leakage,
// TreeNode* should be replaced with shared_ptr.
StackElem(int s1, int s2, int l, int v=0): start1(s1), start2(s2), length(l), node(new TreeNode(v)) {}
};
};
__________________________________________________________________________________________________