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

那麼，今天就讓我們來解決 nary 樹的後序遍歷問題。

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.

這是最常見的情況，每個節點最多有兩個子節點。

So something like this.

是以，可以這樣說

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

那麼，我們可以放寬有兩個孩子的限制，允許有多個孩子。

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

所以，零個孩子、一個孩子、兩個孩子，然後是更多的孩子。

So three, four, five.

三、四、五

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.

那麼，我們就不能再只有一兩個變量了。

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.

對於兩個節點的遞歸，使用後序遍歷時，我們要做的是先遍歷左邊的子節點，然後遞歸遍歷右邊的子節點，最後遍歷當前節點。

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.

是以，從這裡到一般樹的唯一變化是，這兩個步驟實際上將合併為一個步驟，即運行一個輔助函數，或者對所有子節點進行遞歸。

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.

最後，也就是第二步，其實就是原始節點。

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.

是以，我們可以從這裡返回一個空列表，然後通過遞歸調用進行一系列連接，但我認為更簡單的做法可能是先創建一個像這樣的結果變量，然後再將其返回到這裡。

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.

是以，這裡有兩個步驟。

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.

對於這個問題，我認為我們可以直接從這裡獲取返回值，然後將它們合併到一個列表中，但這樣做效率不高，而且編碼也會更復雜。

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.

對於平衡樹來說，它應該是對數 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.

比方說，我們有三個孩子。

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.

在大多數語言中，這需要兩個堆棧。

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.

這就是為什麼我們要有兩個堆棧。

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.

但是，一旦一個節點已經被訪問過，並且它正在被第二次訪問，這時我們就知道我們實際上已經完成了對該節點的訪問。

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.

是以，我們要做的是四個、三個，我的篇幅不夠了，抱歉，然後是兩個，然後這些都是假的。

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.

是以，如果不是 root，就返回一個空列表。

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.

從堆棧中彈出，我們將得到兩個值。

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

順便說一下，在 Python 中，我使用的是 tuple（元組），即一對值。

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.

不過，如果你願意，也可以有兩個獨立的堆棧。

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

反正它們的長度總是一樣的。

So that works too.

這樣也行得通。

So we pop, we get two things.

是以，我們可以得到兩樣東西。

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.

或者說，實際上，如果它已經被訪問過，那就意味著這是我們第二次看到它。

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.

從技術上講，我們第一次看到這個節點是在開始遞歸調用時，我們檢查它是否為空，然後立即返回。

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.

然後我們再回來，第二次看到相同的節點時，我們就會在遍歷子節點後將其追加到結果中。

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.

感謝您的收看，再見。