Problem
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Solution
Simple post order traversal problem. Could be solved with trivial recursive method or iterative.
Implementation
Recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
void runner(TreeNode* root, vector<int>& output) {
if (!root) return;
runner(root->left, output);
runner(root->right, output);
output.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> output;
runner(root, output);
return output;
}
};
Iterative - 2 Stacks
Traverse the tree and read the traversed nodes backwards using stack.
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
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> output;
if (!root) return output;
stack<TreeNode*> temp;
stack<int> traversed;
temp.push(root);
while(!temp.empty()) {
TreeNode* cur = temp.top();
temp.pop();
traversed.push(cur->val);
if (cur->left) temp.push(cur->left);
if (cur->right) temp.push(cur->right);
}
while(!traversed.empty()) {
output.push_back(traversed.top());
traversed.pop();
}
return output;
}
};
Iterative - 1 Stack
Only use 1 stack to keep track of the traversed nodes. Demolishes the tree along the way to stop the algorithm from visiting the same node again.
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
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> temp;
vector<int> output;
if (!root) return output;
temp.push(root);
while (!temp.empty()) {
TreeNode* cur = temp.top();
if (cur->left) {
temp.push(cur->left);
cur->left = nullptr;
}
else if (cur->right) { // left is nullptr
temp.push(cur->right);
cur->right = nullptr;
}
else { // visit
output.push_back(cur->val);
temp.pop();
}
}
return output;
}
};