This is one of those problems where the clean idea matters more than the amount of code. For 606. Construct String from Binary Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. 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: two pointers, stack, sliding window.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are tree2str.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- 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:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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/**
02You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.
03
04The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.
05
06Example 1:
07Input: Binary tree: [1,2,3,4]
08 1
09 / \
10 2 3
11 /
12 4
13
14Output: "1(2(4))(3)"
15
16Explanation: Originallay it needs to be "1(2(4)())(3()())",
17but you need to omit all the unnecessary empty parenthesis pairs.
18And it will be "1(2(4))(3)".
19Example 2:
20Input: Binary tree: [1,2,3,null,4]
21 1
22 / \
23 2 3
24 \
25 4
26
27Output: "1(2()(4))(3)"
28
29Explanation: Almost the same as the first example,
30except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
31**/
32
33//Runtime: 44 ms, faster than 58.66% of C++ online submissions for Construct String from Binary Tree.
34//Memory Usage: 56.2 MB, less than 30.85% of C++ online submissions for Construct String from Binary Tree.
35/**
36 * Definition for a binary tree node.
37 * struct TreeNode {
38 * int val;
39 * TreeNode *left;
40 * TreeNode *right;
41 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
42 * };
43 */
44class Solution {
45public:
46 string tree2str(TreeNode* t) {
47 string ans = "";
48
49 if(!t) return ans;
50
51 ans = to_string(t->val);
52 if(t->left && t->right){
53 ans += "(" + tree2str(t->left) + ")";
54 ans += "(" + tree2str(t->right) + ")";
55 }else if(t->left && !t->right){
56 ans += "(" + tree2str(t->left) + ")";
57 }else if(!t->left && t->right){
58 ans += "()";
59 ans += "(" + tree2str(t->right) + ")";
60 }
61
62 return ans;
63 }
64};
65
66/**
67Approach #1 Using Recursion [Accepted]
68This solution is very simple. We simply need to do the preorder traversal of the given Binary Tree.
69But, along with this, we need to make use of braces at appropriate positions.
70But, we also need to make sure that we omit the unnecessary braces.
71To do the preorder traversal, we make use of recursion.
72We print the current node and call the same given function for the left and the right children of the node in that order(if they exist).
73For every node encountered, the following cases are possible.
74
75Case 1: Both the left child and the right child exist for the current node.
76In this case, we need to put the braces () around both the left child's preorder traversal output
77and the right child's preorder traversal output.
78
79Case 2: None of the left or the right child exist for the current node.
80In this case, as shown in the figure below, considering empty braces for the null left and right children is redundant.
81Hence, we need not put braces for any of them.
82
83No_child
84
85Case 3: Only the left child exists for the current node.
86As the figure below shows, putting empty braces for the right child in this case
87is unnecessary while considering the preorder traversal.
88This is because the right child will always come after the left child in the preorder traversal.
89Thus, omitting the empty braces for the right child also leads to same mapping between the string and the binary tree.
90
91Left_child
92
93Case 4: Only the right child exists for the current node.
94In this case, we need to consider the empty braces for the left child.
95This is because, during the preorder traversal, the left child needs to be considered first.
96Thus, to indicate that the child following the current node is a right child we need to put a pair of empty braces for the left child.
97
98Right_child
99
100Just by taking care of the cases, mentioned above, we can obtain the required output string.
101
102
103Complexity Analysis
104
105Time complexity : O(n)O(n). The preorder traversal is done over the nn nodes of the given Binary Tree.
106
107Space complexity : O(n)O(n). The depth of the recursion tree can go upto nn in case of a skewed tree.
108**/
109
110/**
111Approach #2 Iterative Method Using stack [Accepted]
112Algorithm
113
114In order to solve the given problem, we can also make use of a stackstack. To see how to do it, we'll go through the implementation and we'll also look at the idea behind each step.
115
116We make use of a stackstack onto which various nodes of the given tree will be pushed during the process. The node at the top of the stackstack represents the current node to be processed. Whenever a node has been processed once, it is marked as visited. The reasoning behind this will be discussed soon.
117
118We start off by pushing the root of the binary tree onto the stackstack. Now, the root acts as the current node. For every current node encountered, firstly, we check if it has not been visited already. If not, we add it to the set of visited nodes.
119
120Since, for the preorder traversal, we know, we need to process the nodes in the order current-left-right. Thus, we add a ( followed by the current node to the string ss to be returned.
121
122Now, if both the left and the right children of the current node exist, we need to process them in the order left-right. To do so, we need to push them onto the stackstack in the reverse order, so that when they are picked up later on, their order of processing gets corrected.
123
124Since we've already added (current\_node(current_node to the string ss, if only the right child of the current node exists, as discussed in case 4 in the last approach, we need to put a () in ss representing the null left node. We need not push anything onto the stackstack for the left node and we can directly add the () to ss for this. But, we still need to push the right child onto the stackstack for future processing.
125
126If only the left child exists, we need not consider the right child at all, as discussed in case 3 in the last approach. We can continue the process by just pushing the left child onto the stackstack.
127
128Now, we need to note that even when a node is being processed, if it has not already been visited, it isn't popped off from the stackstack. But, if a node that has already been processed(i.e. its children have been considered already), it is popped off from the stackstack when encountered again. Such a situation will occur for a node only when the preorder traversal of both its left and right sub-trees has been completely done. Thus, we need to add a ) to mark the end of the preorder traversal of the current node as well.
129
130Thus, at the end, we get the required pre-order traversal in the substring s(1:n-1)s(1:n−1). Here, nn represents the length of ss. This is because, we need not put the parentheses(redundant) at the outermost level.
131
132The following animation better depicts the process.
133**/
134
135/**
136Complexity Analysis
137
138Time complexity : O(n)O(n). nn nodes are pushed and popped in a stack.
139
140Space complexity : O(n)O(n). stackstack size can grow upto nn.
141**/
142
143//Runtime: 32 ms, faster than 79.03% of C++ online submissions for Construct String from Binary Tree.
144//Memory Usage: 22.1 MB, less than 94.68% of C++ online submissions for Construct String from Binary Tree.
145
146/**
147class Solution {
148public:
149 string tree2str(TreeNode* t) {
150 if(!t) return "";
151
152 string s = "";
153 stack<TreeNode*> stk;
154 set<TreeNode*> visited;
155
156 stk.push(t);
157 while(!stk.empty()){
158 t = stk.top();
159 if(visited.find(t) == visited.end()){
160 visited.insert(t);
161 //to_string(int): string
162 s += ("(" + to_string(t->val));
163 if(!t->left && t->right){
164 s += "()";
165 }
166 if(t->right){
167 stk.push(t->right);
168 }
169 if(t->left){
170 stk.push(t->left);
171 }
172 }else{
173 stk.pop();
174 s += ")";
175 }
176 }
177
178 //s.substr(start, length)
179 return s.substr(1, s.size()-2);
180 }
181};
182**/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.