-
Notifications
You must be signed in to change notification settings - Fork 0
/
(2 diff Soln. ) Binary Tree Postorder Traversal
39 lines (37 loc) · 1.38 KB
/
(2 diff Soln. ) Binary Tree Postorder Traversal
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
// problem url: https://leetcode.com/problems/binary-tree-postorder-traversal/submissions/
// mode: Easy
// Binary Tree PostOrder Traversal :: ( 2 Soln. :: Recursive and Iterative)
//################################################################## Recursive ##########################################################################################
class Solution {
public:
void traverse(TreeNode* root, vector<int> &ans){
if(root==nullptr)
return;
if(root->left) traverse(root->left, ans);
if(root->right) traverse(root->right, ans);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
traverse(root, ans);
return ans;
}
};
//################################################################## Iterative ###########################################################################################
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if(root) st.push(root);
while(!st.empty()){
TreeNode* topNode = st.top();
st.pop();
ans.push_back(topNode->val);
if(topNode->left) st.push(topNode->left);
if(topNode->right) st.push(topNode->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};