[LeetCode] 590. N-ary Tree Postorder Traversal

 

https://leetcode.com/problems/n-ary-tree-postorder-traversal/description/?envType=daily-question&envId=2024-08-26

leetcode - N-ary Tree Postorder Traversal

문제 유형 : 트리, dfs, 재귀, 스택

문제 난이도 : Easy

 

문제

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)

 

n진트리의 루트가 주어진다. 후위 순회를 하여 노드의 값들을 순서대로 반환하시오.

n진트리의 입력 직렬화는 그들의 레벨에 맞게 대표될 것이다. 각 자식노드의 그룹은 null로 나눠진다. (사이트의 예시 참고)

 

풀이

1. 재귀를 이용

후위 순회는 항상 (왼쪽자식) ~ (오른쪽 자식), (루트)이다.

즉, 1번째자식 -> 2번째자식 -> ... -> n번째자식 -> 루트로 정답 배열에 저장시키면 된다

 

2. 반복문과 스택을 이용

후위 순회의 역순으로 순회를 할 것이다.

즉, (루트) -> n번째자식 -> n-1번째 자식 -> ... -> 1번째자식 순으로 정답 배열에 저장시킨 뒤,

정답 배열을 뒤집어주면 된다.

 

 

코드

C++ - 재귀를 이용한 풀이

// Definition for a Node.
/*
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
private:
    void traverse(Node* root, vector<int>& ans) {
        if(!root) return;
        for(const auto &child : root -> children) {
            traverse(child, ans);
        }
        ans.push_back(root -> val);
    }
public:
    vector<int> postorder(Node* root) {
        vector<int> ans;
        traverse(root, ans);
        return ans;
    }
};

 

GO - 재귀 없이 반복문을 이용한 풀이

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    if root == nil {
        return nil
    }
    
    var stack []*Node
    var ans []int

    stack = append(stack, root)
    for len(stack) > 0 {
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        ans = append(ans, curr.Val)
        
        for _, child := range curr.Children {
            stack = append(stack, child)
        }
    }
    
    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
        ans[i], ans[j] = ans[j], ans[i]
    }
    
    return ans
}