[LeetCode] 145. Binary Tree Postorder Traversal c++

• 문제

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

출처 : https://leetcode.com/problems/binary-tree-postorder-traversal/

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

 

• 문제 해결

vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    if(root){
        stk.push(root);
    }

    vector<int> ans;
    while(stk.size()){
        auto p = stk.top();
        if(p == nullptr){
            stk.pop();
            ans.push_back(stk.top()->val);
            stk.pop();
            continue;
        }
        stk.push(nullptr);
        if(p->right){
            stk.push(p->right);
        }
        if(p->left){
            stk.push(p->left);
        }
    }
    return ans;
}

 

 

다른 방법

class Solution {
private:
    void postorder(TreeNode* curr, vector<int>& vec){
        if(!curr){
            return;
        }
        
        postorder(curr->left, vec);
        postorder(curr->right, vec);
        
        vec.push_back(curr->val);
        return;
    }
    
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> vec;
        postorder(root, vec);
        
        return vec;
    }
};