145. Binary Tree Postorder Traversal

Input: root = [1,null,2,3]
Output: [3,2,1]
Input: root = []
Output: []
Input: root = [1]
Output: [1]
Input: root = [1,2]
Output: [2,1]
Input: root = [1,null,2]
Output: [2,1]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {

vector<int> v;
if(root == NULL){
return v;
}
postorder(root, v);
return v;
}
void postorder(TreeNode* root, vector<int> &v){
if(root == NULL){
return;
}
postorder(root->left, v);
postorder(root->right, v);
v.push_back(root->val);
}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
res.insert(res.begin(), p->val);
p = p->right;
} else {
TreeNode *t = s.top(); s.pop();
p = t->left;
}
}
return res;
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store