[LeetCode] 590. N-ary Tree Postorder Traversal c++

• 문제

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

 

Example 1:

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

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

 

• 문제 해결

DFS문제

 

class Solution {
public:
    vector<int> postorder(Node* root) {
        if(!root){
            return {};
        }
        std::stack<std::pair<Node *, int>> s;
        std::vector<int> res;
        s.emplace(root, 0);
        while(!s.empty()){
            auto &[node, index] = s.top();   // C++17 이상 버전에서만 적용
            if(index == node->children.size()){
                res.push_back(node->val);
                s.pop();
            }
            else{
                s.emplace(node->children[index++], 0);
            }
        }
        return res;
    }
};

auto &[node, index] = s.top();

→ 이 람다 표현식은 C++17 이상 버전에서만 적용되는 문법이다.

17 하위 버전을 사용하고 있다면 

  auto& node = s.top().first;
  auto& index = s.top().second;

위 코드로 사용하면 된다.