【刷题日记】590. N 叉树的后序遍历

本次刷题日记的第 5 篇，力扣题为：【刷题日记】590. N 叉树的后序遍历 ，简单

一、题目描述：

乍一看到这个题，有没有感觉很熟悉，仿佛就在上一篇文章中做过

xdm ，你的感觉没错，这个题内容就是和上一题一毛一样，只不过是把之前多叉树的前序遍历，在此处换成了多叉树的后序遍历

对于上一篇，看明白的朋友们，相信做这道遍历后序的题（【刷题日记】589. N 叉树的前序遍历），绝对难不倒你，相信不

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

之前有分享过什么是二叉树 / 多叉树的 前序遍历，中序遍历，后序遍历，二叉树的后序遍历就是先遍历左子树，再遍历右子树，最后遍历根

对于多叉树来说就是，先遍历多叉树的孩子节点，再遍历根节点

那么对于今天的多叉树的后序遍历来说，我们也可以用示例推演一下，一起走过一遍，这种对于树的递归遍历，都是大同小异了

我们仍然还是用题中的实例作为推演，

输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]

相信上图的演示能够让你看明白，每一个节点是如何加入到结果集的，多叉树的后序遍历，按照左右根的方式来进行递归遍历，你也可以很快很轻松的完成

2、尝试编码

根据上述的推演和分析，我们只需要一棵子树一棵子树的去按照 左右根 的方式进行遍历即可

func postorder(root *Node) (ans []int) {
    var dfs func(*Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        // 先遍历孩子节点
        for _, ch := range node.Children {
            dfs(ch)
        }
        // 再把根节点加入到结果集中
        ans = append(ans, node.Val)
    }
    dfs(root)
    return
}

看了上述编码，有没有发现和前序遍历就是部分代码顺序的调整？实际上也确实是这样的，如果还有没有明白的地方，可以多多推演几次就能明白了

四、总结：

上述做法和多叉树的前序遍历做法基本一致，so ， 对于时间复杂度和空间复杂度也是一样的

时间复杂度是 O(m) ， 这个 m 表示的是 多叉树的节点个数

空间复杂度是 O(m)

原题地址：590. N 叉树的后序遍历

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~