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つの子を持つ。

So something like this.

だから、こんな感じだ。

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 three, four, five.

だから3、4、5だ。

It could be unbounded.

無制限かもしれない。

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.

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

We're going to be given a current node.

現在のノードが与えられる。

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

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

So if not node, then just return.

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

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.

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

So here, remember, there's two steps.

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

We're going to go through every child.

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

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.

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

Let's run it.

走らせてみよう。

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

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

So let me do that on the root.

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

Really sorry about that.

本当に申し訳ない。

Okay, there you go.

よし、これでいい。

It works.

うまくいっている。

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はツリーの高さ）。

For a balanced tree, it should be log N.

バランスの取れたツリーの場合、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 let's do it.

だから、そうしよう。

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.

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

We have three children, let's say.

私たちには3人の子供がいる。

So here, we want to do this guy.

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

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.

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

That's going to be with a Boolean value.

これはブール値になる。

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

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

Pre-order would be pretty easy.

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

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.

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

So that's what the stack would be for.

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

We wouldn't add this to the stack.

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

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.

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

That would be pre-order.

それは予約注文だろう。

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.

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

So how do we do that?

では、どうすればいいのか？

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.

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

That's fine.

それでいい。

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つ用意し、未訪問とする。

So it's false.

だから嘘だ。

That's what we're going to pop first.

それを最初に弾くんだ。

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.

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

We're probably going to do it in reverse order.

おそらく逆の順番でやることになるだろう。

So we do this four, three, I'm running out of space, sorry, and then two, and then these would all be false.

つまり、4つ、3つ、スペースがないのでごめんなさい、そして2つ、そしてこれらはすべて偽となる。

And then we'd pop this one most recently.

そして、直近ではこれを弾く。

That's why we added it last, because it's two.

だから最後に追加したんだ。

That's the one that we'd want to go through first.

まず、それを経験したい。

So we'd pop this, we'd see this hasn't been visited yet either.

だから、これをポップすると、ここもまだ訪問されていないことがわかる。

So we'd add it back to the stack, and we'd add its children.

だから、スタックに戻し、その子を追加する。

And you can continue with this.

そして、これを続けることができる。

Eventually, we'll have gone through all of these, and then we'll get to this guy.

最終的には、これらすべてを経て、この男にたどり着くだろう。

And this will be the last one that we pop.

そして、これが最後のポップになる。

This is the last item in our stack.

これがスタックの最後の項目だ。

So it makes sense that it is the root of our tree.

だから、木の根っこというのは理にかなっている。

So that's the idea.

そういうことだ。

Let's go ahead and code this up.

さっそくコードを書いてみよう。

Okay, so I'll actually leave this code here, because I'm pretty sure my solution will be pretty similar.

オーケー、では実際にこのコードをここに残しておこう。私の解決策も似たようなものになるだろうから。

So here, I'm going to start the stack like this, with just the root, and we're going to say false, it hasn't been visited yet.

ここでは、このようにルートだけでスタックを開始し、falseとします。

And it's actually technically possible that the root could be null.

そして、技術的にはルートがヌルである可能性もある。

So my code isn't really going to handle that elegantly.

だから、私のコードではそれをエレガントに処理することはできない。

So I think the best way to handle that is just with an if statement.

だから、if文で処理するのがベストだと思う。

So if not root, go ahead and return an empty list.

ルートでない場合は、空のリストを返す。

Otherwise, let's go through the stack.

そうでなければ、スタックを見てみよう。

While stack, we're going to pop.

スタックしている間に、弾くんだ。

So pop from this stack, and we're going to get two values.

このスタックからポップすると、2つの値が得られる。

By the way, in Python, I am using a tuple, a pair of values.

ちなみに、Pythonではタプル（値のペア）を使っている。

You could probably do that in other languages as well that have like a pair class.

ペアクラスがあるような他の言語でも同じことができるだろう。

But if you wanted to, you could also just have two separate stacks.

しかし、その気になれば、スタックを2つに分けることもできる。

They're always going to be of the same length anyway.

どうせいつも同じ長さになるんだ。

So that works too.

だからそれも有効だ。

So we pop, we get two things.

つまり、2つのものを手に入れることができる。

We get the node, and we get if it's been visited or not.

ノードを取得し、それが訪問されたかどうかを取得する。

If it's not been visited, this is what we do.

未訪問なら、こうする。

Or actually, if it has already been visited, that means this is the second time we're seeing it.

というか、すでに訪れているのなら、今回が2度目ということになる。

So then we're just going to take its value and append it to the result.

つまり、その値を結果に追加するだけだ。

So result.appendNode.value.

だからresult.appendNode.value。

And you can see that this is actually analogous to what we did in the recursive solution down here.

そして、これは再帰的解法でやったことに似ていることがわかるだろう。

Technically, the first time we see this node is when we start the recursive call and we check if it's null, we return immediately.

厳密には、このノードを最初に見るのは再帰呼び出しを開始したときで、nullかどうかをチェックしてすぐに戻る。

Then we go through all of its children.

そして、その子供たちをすべて見ていく。

And then we come back and the second time we see that same node, that's when we actually append it to the result after we've gone through the children.

そしてまた戻ってきて、2度目に同じノードを見たときに、子ノードを経由した後に、実際にそのノードを結果に追加する。

So that's what we're doing up here as well.

だから、ここでもそうしているんだ。

So we have one case where it was visited and we have the other case where it's not been visited.

つまり、訪問されたケースと訪問されていないケースがある。

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

だから、スタックに戻すんだ。

So a stack.append this node, but this time mark it as visited.

そこで、スタックはこのノードを追加するが、今回は訪問済みとしてマークする。

So first it was false.

だから最初は嘘だった。

Now it's going to be true and go through all of the children for c in node.children, add them to the stack as well.

これでtrueになり、node.childrenにあるcのすべての子を調べ、スタックに追加する。

So c and mark them as false.

だから、cを付けて偽とする。

They haven't been visited.

彼らはまだ訪れていない。

This is the first time they're being added to the stack.

スタックに追加されるのは今回が初めてだ。

And then after all of this, we can just return the result.

そして、このすべてが終わったら、結果を返せばいい。

There's only one problem with this.

これにはひとつだけ問題がある。

And remember, it's the order.

そして忘れてはならないのは、それが順番だということだ。

The order that we add the children in does matter.

子供たちを加える順番は重要だ。

So I think in this case, we want to do it in reverse order in Python.

だからこの場合、Pythonでは逆の順序でやりたいんだと思う。

That's pretty easy to fix here.

ここで修正するのは簡単だ。

We can just add colon colon minus one.

コロン・コロン・マイナス1を加えればいいのだ。

This basically goes through the list in reverse order.

これは基本的にリストを逆順に見ていく。

I think we're good here.

ここでいいと思う。

Let's go ahead and run this.

さっそく実行してみよう。

And as you can see, it works.

見ての通り、うまくいっている。

It's pretty efficient.

かなり効率的だ。

This is the iterative solution.

これが反復解法である。

The time and space complexity, I believe, is the same.

時間と空間の複雑さは同じだと思う。

If you found this helpful, check out neatcode.io for a lot more.

これが役に立ったと思ったら、他にもたくさんあるのでneatcode.ioをチェックしよう。

Thanks for watching and I'll see you soon.

見てくれてありがとう。