Name: N-ary木のポストオーダートラバーサル - リートコード 590 - Python (N-ary Tree Postorder Traversal - Leetcode 590 - Python)
Uploaded: 2024-08-26T06:03:54.000Z
Duration: 9 min 50 s

Hey everyone, welcome back, and let's write some more neat code today.

みんな、おかえりなさい。今日もすてきなコードを書こう。

So today, let's solve the problem, n-ary tree post-order traversal.

というわけで、今日はn元木の後置走査という問題を解いてみよう。

様態の副詞

So the idea is basically, if you know what a regular tree is, well, when I say regular, I mean binary.

つまり、基本的な考え方は、普通の木がどういうものか知っているのであれば、普通の木というのはバイナリーのことだ。

That's kind of the most common, where each node will have at most two children.

これは最も一般的な方法で、各ノードは最大でも2つの子を持つ。

Well, we could relax that constraint of having two children and allow multiple children.

まあ、子供が2人という制約を緩和して、複数の子供を認めることもできる。

So zero children, one children, two, and then more than that.

だから、子供はゼロ、1人、2人、そしてそれ以上。

So what kind of data structure do you think we should use to store all of the children of a particular node?

では、特定のノードのすべての子を保存するために、どのようなデータ構造を使うべきだと思いますか？

Well, we can't just have one or two variables for that anymore.

まあ、そのために1つか2つの変数を持っているわけにはいかなくなった。

So now we probably need something like an array, and that's exactly what we're going to have.

だから、配列のようなものが必要だろう。

In most languages, we're going to have like a resizable list as the children variable for a node object now.

ほとんどの言語では、リサイズ可能なリストをノード・オブジェクトの子変数として持つことになる。

So imagine you have multiple children for a node.

あるノードに複数の子ノードがあるとしよう。

Well now, how do you do the post-order traversal?

では、ポストオーダー・トラバーサルをどのように行うのか？

Remember, post-order traversal just means you will only visit a node after all of its children have been visited, and that's going to be recursive.

覚えておいてほしいのは、ポストオーダー・トラバーサルとは、あるノードの子ノードがすべて訪問された後に、そのノードを訪問するということであり、それは再帰的になるということだ。

So that applies for all of these nodes as well.

だから、これらのすべてのノードにも当てはまる。

So basically, we're going to do all of the descendants of a single node, and then we'll pop back up to the parent, and then do all the other descendants of that node, and then we'll do the parent.

だから基本的には、ひとつのノードの子孫を全部やって、それから親にポップアップして、そのノードの他の子孫を全部やって、それから親をやる。

Recursively, with two nodes, with post-order traversal, what we would do is do the left child, then recursively do the right child, and then lastly, do the current node.

再帰的に、2つのノードがある場合、後順序トラバーサルを使うと、左の子を処理し、次に右の子を再帰的に処理し、最後に現在のノードを処理することになる。

So the only thing that's going to change from here to the general tree is that these two steps are actually going to be merged into a single step, and that's going to be run a helper function or just recursively on the children, all of them.

つまり、ここから一般的なツリーに変更されるのは、この2つのステップが1つのステップに統合され、ヘルパー関数を実行するか、すべての子プロセスを再帰的に実行するということだけです。

And I think the order does matter, so we probably want to do the leftmost child first, and then the next one, and then the next one.

順番は重要だと思うので、おそらく一番左の子を最初にやって、次に次の子、さらにその次の子とやっていきたい。

So do that, and then lastly, or the second step, really is just the original node.

そうして、最後に、あるいは2番目のステップで、元のノードに戻す。

So it's pretty much the same recursively.

だから、再帰的にはほとんど同じだ。

I'll also do this iteratively for you as well.

これも繰り返しやってあげよう。

The time and space complexity, I think, is going to be the same, but let's solve this recursively now.

時間と空間の複雑さは同じになると思うが、今これを再帰的に解いてみよう。

So I'm going to create the helper function down here, and that's what I'm going to call it.

この下にヘルパー関数を作り、それをこう呼ぶことにする。

The base case is the same as pretty much every recursive tree problem.

基本ケースは、ほとんどすべての再帰木問題と同じである。

だから、もしノードでなければ、戻るだけだ。

There's no need to return anything, because what we want to do is basically collect all the values of every node, and then put them in a list, and then return that.

何も返す必要はない。やりたいことは、基本的にすべてのノードの値を集めてリストにまとめ、それを返すことだからだ。

So from here, we could return an empty list from here, and then do a bunch of joining with the recursive call, but I think it's probably just easier to have a variable like this result, and then we can just return that out here.

だから、ここから空のリストを返して、再帰呼び出しでたくさんの結合を行うこともできるが、このresultのような変数を用意して、それをここで返すほうが簡単だろう。

And then within the function, we can modify that.

そして、関数内でそれを修正することができる。

We could have made it a member variable if we needed to, but I didn't.

必要ならメンバー変数にすることもできたが、私はそうしなかった。

ここで、2つのステップがあることを思い出してほしい。

子供たち全員を調べるつもりだ。

So for a child in node.children, that is the data type that's given to us.

つまり、node.childrenの子には、そのデータ型が与えられる。

I think it should be a list type, but in Python, it's kind of ambiguous.

リスト型であるべきだと思うが、Pythonでは曖昧だ。

And then so for all the children, we're going to run the helper function recursively on them, and then after that's done, to the result, we want to append the current node's value, so node.value.

そして、すべての子ノードに対してヘルパー関数を再帰的に実行し、それが終わった後に、現在のノードの値をnode.valueに追加する。

With this problem, I think we could have just gotten the return values from here, and then joined them into a single list, but that wouldn't have been as efficient, and it would have been more complicated to code that up as well.

この問題では、ここから戻り値を取得して、それらを1つのリストに結合することもできたと思うが、それでは効率が悪いし、コード化も複雑になるだろう。

So this is, I think, the working solution.

だから、これが現実的な解決策だと思う。

Okay, well, I promise you it would be the working solution if we didn't forget to actually call the helper function.

さて、ヘルパー関数を実際に呼び出すことを忘れなければ、この方法で解決することは約束しよう。

では、根元でやらせてもらおう。

This is technically the most efficient solution.

これは技術的に最も効率的な解決策である。

We're just going to go through every node in the tree.

ツリー内のすべてのノードを調べていく。

So in terms of the time complexity, it would have been big O of N.

だから、時間の複雑さという点では、NのビッグOだっただろう。

In terms of the memory complexity, it still would have been big O of H, where H is the height of the tree.

メモリの複雑さという点では、それでもHの大きなOになっただろう（Hはツリーの高さ）。

バランスの取れたツリーの場合、log Nとなる。

It should be log where the base is, I guess, the branching factor, if that's the correct term for this.

ベースはログであるべきで、それが正しい用語であるならば、分岐係数だと思う。

But anyways, let's now do the iterative solution, actually.

とにかく、反復解法をやってみよう。

And I'll quickly walk you through how we're going to do it.

早速、その方法を説明しよう。

The time and space complexity, though, is going to be the same.

しかし、時間と空間の複雑さは変わらない。

I just think it's interesting to solve this iteratively.

ただ、これを繰り返し解くのは面白いと思うんだ。

Sometimes that can be asked in interviews.

So we kind of just talked about how to do this recursively.

だから、再帰的なやり方について話しただけだ。

Well, doing it iteratively isn't too much different.

まあ、反復的にやっても大差はない。

It's definitely not much different from just doing it on a regular binary tree, but let's still imagine we have multiple children.

普通のバイナリツリーでやるのと大差ないのは確かだが、それでも複数の子供がいることを想像してみよう。

だからここで、この男をやりたいんだ。

So if we were doing this iteratively, usually we have a stack, and that's what we're going to have this time.

だから、もしこれを繰り返しやるなら、普通はスタックがある。

But I'll just kind of spoil this for you.

でも、ちょっとだけネタバレしておこう。

This is, in most languages, going to require two stacks.

ほとんどの言語では、これは2つのスタックを必要とする。

One stack where we actually add the node itself, and then another stack where we mark if that node has been visited or not.

ノードそのものを追加するスタックと、そのノードが訪問済みかどうかをマークするスタックがある。

And the reason for that is, imagine we were just doing this pre-order style, or even if we're doing this in order.

その理由は、もし私たちがこの予約注文のスタイルで、あるいは順番にやっていると想像してみてください。

予約注文はかなり簡単だろう。

That would mean taking this node, visiting it, and then we want to go through all of the children.

つまり、このノードを訪問し、すべての子ノードを見て回るということだ。

Well, that's what we're going to need the stack for, because for us to say, okay, we'll go through all the children.

そのためにはスタックが必要なんだ。

First, we want to go to this child, and then do all of its descendants.

まず、この子に行き、そのすべての子孫に行く。

And then eventually we want to come back here.

そしていずれはここに戻ってきたい。

そのためのスタックというわけだ。

これをスタックに加えることはない。

We would add these guys to the stack in that order.

この順番でスタックに加える。

Well, maybe this time it would be in reverse order, because we'll pop the last thing that was added to the stack.

スタックに最後に追加されたものをポップするからだ。

In order would be pretty similar as well, except that time we would add this to the stack, and then go left.

順番もよく似ているが、スタックにこれを追加し、左に進む。

And then eventually we'd pop back here, and then we'd go right.

そして最終的にはここに戻ってきて、右に行くんだ。

Well, with post-order, it's a little bit unique.

まあ、ポストオーダーというのはちょっと特殊なんだ。

I think post-order is the hardest one to do, even with just a regular binary tree.

普通のバイナリーツリーでも、ポストオーダーが一番難しいと思う。

And that's because when we get to this node, we want to actually do this node last.

それは、このノードに到達したら、このノードを最後にやりたいからだ。

Well, we add this to the stack, and then we go through its children.

さて、これをスタックに追加し、その子を調べていく。

Okay, but if you try that, then you're going to go through the children, and you're going to end up adding, let's say, this guy also to the stack.

オーケー、でもそうしようとすると、子供たちを経由して、例えばこいつもスタックに加えることになる。

And then when you pop this from the stack, there's no guarantee that all of its descendants have been visited, because we're going to be adding these guys first, and then adding the descendants.

そして、スタックからこれをポップするとき、そのすべての子孫が訪問済みである保証はない。

Since we're popping first in, first out, these are going to be popped before their children are popped.

我々は先入れ先出しなので、これらの選手はその子供たちよりも先に飛び出すことになる。

So that's why we're going to have two stacks.

だからスタックを2つにするんだ。

Sometimes we're going to pop a node, and it hasn't been visited before.

あるノードをポップすることがあるが、そのノードはこれまで一度も訪れたことがない。

But once a node has already been visited, and it's being visited for the second time, that's when we know we're actually finished with that node.

しかし、あるノードがすでに訪問され、2度目に訪問された時点で、そのノードの訪問が実際に終了したことがわかる。

So just to quickly dry run this, I'll give some numbers to these nodes.

では早速、これらのノードの数字を挙げてみよう。

Initially, we're going to have the node one, and we're going to say it hasn't been visited.

最初はノードを1つ用意し、未訪問とする。

And then we're going to see that it was not already visited.

そして、すでに訪問されていないことを確認する。

So this time we're going to add it back to the stack.

だから、今回はスタックに戻す。

And this time we're going to mark it visited, and we're going to take its children, and then add them to the stack now too.

そして今回は、それを訪問済みとマークし、その子もスタックに追加する。