【LeetCode】 589. N-ary Tree Preorder Traversal 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, 再帰
終わりに

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

再帰処理を行う
関数を定義する

この記事で得られること

再帰的な関数について学べる

この記事が役立ちそうな方

再帰処理を練習したい方

詳細

問題

原文

Given the root of an n-ary tree, return the preorder 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:

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

1
2

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

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

1
2

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].

0 <= Node.val <= 10⁴

The height of the n-ary tree is less than or equal to 1000.

Follow up: Recursive solution is trivial, could you do it iteratively?

内容(和訳)

木であるrootが与えられるので、ノードの値を先行順走査(preorder traversal)で返してください。

※preorder traversalは根→左の子→右の子の順に走査します。

※正しくない可能性があります。

解答

解答1：Python, 再帰

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        #rootがNullの場合
        if root is None:
            #Noneを返す
            return None
        
        #戻り値となるリストを用意
        answer = []        
        #answerにrootの値を入れる
        answer.append(root.val)
        #rootの各子ノードに対して処理を行う
        for i in root.children:
            #preorder_traversl関数を実行
            self.preorder_traversal(i, answer)
        #answerを返す
        return answer
    
    #再帰的に子ノードの値をanswerに入れる関数
    def preorder_traversal(self, node, answer):
        #nodeの値をanswerに入れる
        answer.append(node.val)
        #各子ノードに対してそれぞれ処理
        for i in node.children:
            #もう一度この関数自身を呼び出す
            self.preorder_traversal(i, answer)

"""

# Definition for a Node.

class Node:

def __init__(self, val=None, children=None):

self.val = val

self.children = children

"""

class Solution:

def preorder(self, root: 'Node') -> List[int]:

#rootがNullの場合

if root is None:

#Noneを返す

return None

#戻り値となるリストを用意

answer = []

#answerにrootの値を入れる

answer.append(root.val)

#rootの各子ノードに対して処理を行う

for i in root.children:

#preorder_traversl関数を実行

self.preorder_traversal(i, answer)

#answerを返す

return answer

#再帰的に子ノードの値をanswerに入れる関数

def preorder_traversal(self, node, answer):

#nodeの値をanswerに入れる

answer.append(node.val)

#各子ノードに対してそれぞれ処理

for i in node.children:

#もう一度この関数自身を呼び出す

self.preorder_traversal(i, answer)

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方はこちらへ

前：1502. Can Make Arithmetic Progression From Sequence

次：1588. Sum of All Odd Length Subarrays

LeetCode 解答・解説記事一覧