145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Solution

Approach 1: recursion.

Approach 2: iteration -- essentially preorder traversal, reversed (but make sure to visit the right subtree first before reversal). Can do Morris traversal too.

Approach 3: iteration(python only) -- use an additional flag for each item in the stack to indicate whether the node has been visited. Each node gets put onto the stack twice, unvisited(expand child nodes when popped), and visited(its own value to be appended in the end).

Code (Python)

Approach 1:

class Solution:
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # recursive
        if not root:
            return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

Approach 2:

    def postorderTraversal(self, root):
        # iterative: essentially preorder traversal, reversed
        if not root:
            return []
        result = []
        stack = [root]
        while stack:
            node = stack.pop()
            stack.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return result[::-1]

Approach 3:

    def postorderTraversal(self, root):
        # iterative: use additional marker to see if the top node is visited yet
        if not root:
            return []
        result = []
        stack = [(root, False)] # haven't visited the root node initially
        while stack:
            node, visited = stack.pop()
            if visited:
                result.append(node.val)
            else:
                stack.append((node, True)) # so that node's val gets added eventually
                if node.right:
                    stack.append((node.right, False))
                if node.left:
                    stack.append((node.left, False))
        return result

Code (C++)

Approach 1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// Recursion.
class Solution {
private:
    vector<int> res;
    void doPostorderTraversal(TreeNode* root) {
        if (root == NULL)
            return;
        if (root->left)
            doPostorderTraversal(root->left);
        if (root->right)
            doPostorderTraversal(root->right);
        res.push_back(root->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        doPostorderTraversal(root);
        return res;
    }
};

Approach 2:

// Iteration (reverse left-right-reversed-preorder traversal)
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;

        if (root)
            st.push(root);
        while (!st.empty())
        {
            TreeNode *node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->left)
                st.push(node->left);
            if (node->right)
                st.push(node->right);
        }
        
//        while (root) {
//            res.push_back(root->val);
//            if (root->left)
//                st.push(root->left);
//            root = root->right;
//            if (root == NULL && !st.empty()) {
//                root = st.top();
//                st.pop();
//            }
//        }

//        while (root) {
//            res.push_back(root->val);
//            st.push(root);
//            if (root->right)
//                root = root->right;
//            else {
//                root = NULL;
//                while (!st.empty() && !st.top()->left)
//                    st.pop();
//                if (!st.empty()) {
//                    root = st.top()->left;
//                    st.pop();
//                }
//            }
//        }
        
        std::reverse(res.begin(), res.end());
        return res;
    }
};

Approach 3:

// Iteration.
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode *node = root;
        while (node || !st.empty())
        {
            if (node)
            {
                st.push(node);
                node = node->left;
            }
            else
            {
                node = st.top(); // Here the stack will not be empty.
                TreeNode *right = node->right;
                node->right = NULL;
                if (!right)
                {
                    st.pop();
                    res.push_back(node->val);
                }
                node = right;
            }
        }
        return res;
    }
};

// Iteration.
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root)
            st.push(root);
        while (!st.empty())
        {
            TreeNode *node = st.top();
            if (!node->left && !node->right)
            {
                res.push_back(node->val);
                st.pop();
            }
//            else if (node->left)
//            {
//                st.push(node->left);
//                node->left = NULL;
//            }
//            else if (node->right)
//            {
//                st.push(node->right);
//                node->right = NULL;
//            }

            if (node->right)
            {
                st.push(node->right);
                node->right = NULL;
            }
            if (node->left)
            {
                st.push(node->left);
                node->left = NULL;
            }
        }
        return res;
    }
};