Algorithm
Problem Name: 145. Binary Tree Postorder Traversal
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [3,2,1]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Code Examples
#1 Code Example with C Programming
Code -
C Programming
void traversal(int **p, int *psz, int *pn, struct TreeNode *node) {
if (!node) return;
traversal(p, psz, pn, node->left);
traversal(p, psz, pn, node->right);
if (*psz == *pn) {
*psz *= 2;
*p = realloc(*p, (*psz) * sizeof(int));
//assert(*p);
}
(*p)[(*pn) ++] = node->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
int *p, psz, pn;
psz = 100;
p = malloc(psz * sizeof(int));
//assert(p);
pn = 0;
traversal(&p, &psz, &pn, root);
*returnSize = pn;
return p;
}
Input
root = [1,null,2,3]
Output
[3,2,1]
#2 Code Example with C++ Programming
Code -
C++ Programming
// Iterative
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int>res;
stack < TreeNode*>s;
while(!s.empty() || root){
if(root){
s.push(root->left);
res.push_back(root->val);
root = root->right;
}
else{
root = s.top();
s.pop();
}
}
reverse(res.begin(), res.end());
return res;
}
};
// Recursive
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int>res;
DFS(root, res);
return res;
}
void DFS(TreeNode* root, vector<int>& res){
if(!root) return;
DFS(root->left, res);
DFS(root->right, res);
res.push_back(root->val);
}
};
Input
root = [1,null,2,3]
Output
[3,2,1]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList<>();
Stack < TreeNode> stack = new Stack<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
if (node != null) {
stack.push(node);
result.add(node.val);
node = node.right;
} else {
TreeNode removed = stack.pop();
node = removed.left;
}
}
Collections.reverse(result);
return result;
}
}
Input
root = []
Output
[]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const postorderTraversal = function(root) {
const res = []
traverse(root, res)
return res
};
function traverse(node, arr) {
if(node == null) return
traverse(node.left, arr)
traverse(node.right, arr)
arr.push(node.val)
}
Input
root = []
Output
[]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def postorderTraversal(self, root):
ret, stack = [], root and [root]
while stack:
node = stack.pop()
ret.append(node.val)
stack += [child for child in (node.left, node.right) if child]
return ret[::-1]
Input
root = [1]
Output
[1]