Repository navigation
Expand file tree
/
Copy pathmaxTree.cpp
More file actions
74 lines (66 loc) · 1.5 KB
/
Copy pathmaxTree.cpp
File metadata and controls
74 lines (66 loc) · 1.5 KB
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
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode{
int val;
TreeNode *left, *right;
TreeNode(int v):val(v),left(NULL),right(NULL){}
};
TreeNode* buildTree(const vector<int> &nums){
int size = nums.size();
if(size == 0)return NULL;
vector<TreeNode*> allNodes;
for(int i : nums){
allNodes.push_back(new TreeNode(i));
}
stack<int> simpStk;
vector<int> left(size,-1),right(size,-1);
simpStk.push(-1);
for(int i = 0; i < size; ++i){
while(simpStk.top() != -1 && nums[simpStk.top()] < nums[i]){
simpStk.pop();
}
left[i] = simpStk.top();
simpStk.push(i);
}
stack<int> simpStk2;
simpStk2.push(-1);
for(int i = size-1; i >= 0; --i){
while(simpStk2.top() != -1 && nums[simpStk2.top()] < nums[i]){
simpStk2.pop();
}
right[i] = simpStk2.top();
simpStk2.push(i);
}
TreeNode *ans;
for(int i = 0; i < size; ++i){
if(left[i] == -1 && right[i] == -1){
ans = allNodes[i];
}else if(left[i] == -1){
allNodes[right[i]]->left = allNodes[i];
}else if(right[i] == -1){
allNodes[left[i]]->right = allNodes[i];
}else{
if(nums[left[i]] < nums[right[i]]){
allNodes[left[i]]->right = allNodes[i];
}else{
allNodes[right[i]]->left = allNodes[i];
}
}
}
return ans;
}
void preOrder(TreeNode *root){
if(root == NULL)return ;
cout << root->val << endl;
preOrder(root->left);
preOrder(root->right);
}
int main(int argc, char const *argv[])
{
vector<int> arr{4,3,5,2,6,1,7,9};
TreeNode * ans = buildTree(arr);
preOrder(ans);
return 0;
}