Leetcode Binary Tree Postorder Traversal problem solution

In this Leetcode Binary Tree Postorder Traversal problem solution we have Given the root of a binary tree, return the postorder traversal of its nodes' values.

Problem solution in Python.

def postorderTraversal(self, root):
	def traverse(node):
		if node is None: return []
		l = traverse(node.left)
		r = traverse(node.right)
		return l + r + [node.val] 
	return traverse(root)

Problem solution in Java.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) 
            return new ArrayList<Integer>();
        
        List<Integer> list = new ArrayList<Integer>();
        list.addAll(postorderTraversal(root.left));
        list.addAll(postorderTraversal(root.right));
        list.add(root.val);
        
        return list;
    }
}

Problem solution in C++.

class Solution {
public:

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret; 
        stack<pair<int,TreeNode*>> s; 
        if(root){
            s.push({0,root});
        }
        while(s.size()) {
            auto& x = s.top();
            if(x.first == 0) {
                if(x.second->left){
                    x.first = 1; 
                    s.push({0,x.second->left});
                } else if(x.second->right) {
                    x.first = 2;
                    s.push({0,x.second->right});
                } else {
                    x.first = 2; 
                }
            } else if(x.first == 1) {
                if(x.second->right) {
                    s.push({0,x.second->right});
                }
                x.first = 2; 
            } else {
                ret.push_back(x.second->val);
                s.pop();
            }
        }
        return ret; 
    }
};

Problem solution in C.

int nodeCount(struct TreeNode *root){
    if(!root) return 0;
    return 1 + nodeCount(root->left) + nodeCount(root->right);
}

void postorderTraverse(struct TreeNode *root, int *i, int *postorder){
    if(!root) return;
    postorderTraverse(root->left, i, postorder);
    postorderTraverse(root->right, i, postorder);
    postorder[*i] = root->val;
    (*i)++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = nodeCount(root);
    int *result = (int *)malloc((*returnSize) * sizeof(int));
    int i = 0;
    postorderTraverse(root, &i, result);
    return result;

}