## 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;
}
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[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);
}
};
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[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);
node = node.right;
} else {
TreeNode removed = stack.pop();
node = removed.left;
}
}
Collections.reverse(result);
return result;
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #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)
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #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]
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[1]