Binary Tree Postorder Traversal | Problem No. 145 | LeetCode

Subscribe to my newsletter and never miss my upcoming articles

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] Example 4:

Input: root = [1,2] Output: [2,1] Example 5:

Input: root = [1,null,2] Output: [2,1]

Constraints:

The number of the nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

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

No Comments Yet