3.Post-order Traversal

Post means root at last.

Post-order traversal is to traverse the left subtree first. Then traverse the right subtree. Finally, visit the root.

Postorder traversal is used to delete the tree.

Iterative method

Using Two Stacks

class Solution
{

public:
    vector<int> postorderTraversal(TreeNode *root)
    {
      
        stack<TreeNode *> s1;
        stack<int> s2;
        vector<int> v;
        if(root == NULL){return v;}
        TreeNode *t = NULL;
        s1.push(root);
        while (!s1.empty())
        {

            t = s1.top();
            s2.push(t->val);
            s1.pop();
            if (t->left)
            {
                s1.push(t->left);
            }
            if (t->right)
            {
                s1.push(t->right);
            }
        }

        while (!s2.empty())
        {
            int x = s2.top();
            v.push_back(x);
            s2.pop();
        }

        return v;
    }
};

Recursive Method

class Solution
{
    vector<int> v;

    void postOrder(TreeNode *t)
    {
        if(t==NULL){
            return;
        }
        postOrder(t->left);
        postOrder(t->right);
        v.push_back(t->val);
    }

public:
    vector<int> postorderTraversal(TreeNode *root)
    {

        postOrder(root);
        return v;
    }
};