LeetCode #145. Binary Tree Postorder Traversal

Level: Easy

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

Follow up:

Recursive solution is trivial, could you do it iteratively?

My Solution:

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

        return ans;
    }
};

LeetCode#592

LeetCode#590