I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1028. Recover a Tree From Preorder Traversal, the solution in this repository is mainly a binary search solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: binary search, two pointers, stack, sliding window.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are _recoverFromPreorder, recoverFromPreorder.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 28 ms, faster than 35.18% of C++ online submissions for Recover a Tree From Preorder Traversal.
02//Memory Usage: 20 MB, less than 21.05% of C++ online submissions for Recover a Tree From Preorder Traversal.
03
04/**
05 * Definition for a binary tree node.
06 * struct TreeNode {
07 * int val;
08 * TreeNode *left;
09 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13class Solution {
14public:
15 vector<int> values;
16 vector<int> levels;
17
18 TreeNode* _recoverFromPreorder(int startIndex, int endIndex, int nodeLevel){
19 if(startIndex >= endIndex) return NULL;
20 TreeNode* node = new TreeNode(values[startIndex]);
21
22 vector<int>::iterator startIt = find(levels.begin()+startIndex+1, levels.begin()+endIndex, nodeLevel+1);
23 vector<int>::iterator midIt = find(startIt+1, levels.begin()+endIndex, nodeLevel+1);
24 startIndex = startIt - levels.begin();
25 int midIndex;
26 if(midIt == levels.end()) midIndex = endIndex; //exclusive
27 else midIndex = midIt - levels.begin();
28 //[startIndex, endIndex) is the range of this subtree
29
30 // cout << "start: " << startIndex << ", mid: " << midIndex << ", end: " << endIndex << endl;
31
32 //left subtree
33 node->left = _recoverFromPreorder(startIndex, midIndex, nodeLevel+1);
34 //right subtree
35 if(midIndex != endIndex){
36 node->right = _recoverFromPreorder(midIndex, endIndex, nodeLevel+1);
37 }
38
39 return node;
40 }
41
42 TreeNode* recoverFromPreorder(string S) {
43 if(S.size() == 0) return NULL;
44
45 int dashIndex = S.find('-');
46 TreeNode* root = new TreeNode(stoi(S.substr(0, dashIndex)));
47 int numIndex, tmp;
48 values.push_back(stoi(S.substr(0, dashIndex)));
49 levels.push_back(0);
50
51 while(dashIndex != -1){
52 numIndex = S.find_first_of("0123456789", dashIndex+1);
53 tmp = S.find('-', numIndex+1);
54 if(tmp != -1){
55 values.push_back(stoi(S.substr(numIndex, tmp-numIndex)));
56 }else{
57 values.push_back(stoi(S.substr(numIndex)));
58 }
59 levels.push_back(numIndex - dashIndex);
60 dashIndex = tmp;
61 }
62
63// for(int e : values){
64// cout << e << " ";
65// }
66// cout << endl;
67
68// for(int e : levels){
69// cout << e << " ";
70// }
71// cout << endl;
72
73 vector<int>::iterator startIt = find(levels.begin(), levels.end(), 1);
74 vector<int>::iterator endIt = find(startIt+1, levels.end(), 1);
75 int startIndex = startIt - levels.begin();
76 int endIndex;
77 if(endIt == levels.end()) endIndex = levels.size(); //exclusive
78 else endIndex = endIt - levels.begin();
79 //[startIndex, endIndex) is the range of this subtree
80
81 // cout << "start: " << startIndex << ", end: " << endIndex << endl;
82
83 //left subtree
84 root->left = _recoverFromPreorder(startIndex, endIndex, 1);
85 //right subtree
86 if(endIndex != levels.size()){
87 root->right = _recoverFromPreorder(endIndex, levels.size(), 1);
88 }
89
90 return root;
91 }
92};
93
94//[Java/C++/Python] Iterative Stack Solution
95//https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/discuss/274621/JavaC%2B%2BPython-Iterative-Stack-Solution
96//Runtime: 12 ms, faster than 99.64% of C++ online submissions for Recover a Tree From Preorder Traversal.
97//Memory Usage: 11.1 MB, less than 100.00% of C++ online submissions for Recover a Tree From Preorder Traversal.
98//Time O(S), Space O(N)
99
100/**
101 * Definition for a binary tree node.
102 * struct TreeNode {
103 * int val;
104 * TreeNode *left;
105 * TreeNode *right;
106 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
107 * };
108 */
109class Solution {
110public:
111 TreeNode* recoverFromPreorder(string S) {
112 int level, value;
113 TreeNode* node;
114 stack<TreeNode*> stk;
115
116 //no i++ in this for loop!
117 for(int i = 0; i < S.size();){
118 level = 0;
119 value = 0;
120 //&& i < S.size() is important!
121 for(; S[i]=='-' && i < S.size(); i++){
122 level++;
123 }
124 for(; S[i]!='-' && i < S.size(); i++){
125 value = value * 10 + (S[i] - '0');
126 }
127 // cout << level << " " << value << endl;
128 node = new TreeNode(value);
129 //create connection with one of previous nodes
130 while(stk.size() > level){
131 //when current node is level 1,
132 //we expect that the stack contains only 1 node(at level 0)
133 stk.pop();
134 }
135 // cout << stk.size() << endl;
136 if(!stk.empty()){
137 //set this node as its parent's left or right child
138 if(!stk.top()->left)stk.top()->left = node;
139 else stk.top()->right = node;
140 }
141 //push it into stack
142 stk.push(node);
143 // cout << stk.size() << endl;
144 }
145
146 //to get the very first node
147 while(!stk.empty()){
148 node = stk.top();
149 stk.pop();
150 }
151
152 return node;
153 }
154};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.