leetcode刷题记录-590. N 叉树的后序遍历-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

前言

今天的题目为简单，前两天我们做过前序遍历的题目，这道题给的数据和它是完全一样的，就只是需要的是后序遍历，那么就是需要先去了解一下后序遍历的基本知识。

每日一题

给定一个 n 叉树的根节点 root ，返回其节点值的后序遍历。
n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

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

示例 2：

输入：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]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
复制代码

提示：

节点总数在范围 [0, 104] 内
0 <= Node.val <= 104
n 叉树的高度小于或等于 1000

题解

后序遍历

前两天我们刚做过一道前序遍历的题目，那么一样的，我们需要先来了解一下什么是后序遍历。

后序遍历（LRD）是[二叉树遍历]的一种，也叫做[后根遍历]、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。

在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

接着我们拿一棵实际的树来看一下什么是后序遍历：

假设我们现在有一棵上面这样的树，那么按照后序遍历的遍历顺序，我们就应该先去找左子树然后去找右子树，最后才是根节点。那么上面这个树的后序遍历就应该是 [4,5,2,3,6,1]。

我们先去遍历找到最深的左孩子，也就是 4，接着找它的右孩子，也就是 5，最后才是它的根节点 2，并且 2 又是 1 的左孩子，所以下一个节点就是 2，那么就遍历完了根节点 1 的左孩子，接着要去遍历他的右孩子，也就是 3 这个子树，剩下的就是和 2 子树一样的步骤了，最后才会到根节点 1，我们就能够得到上面的后序遍历。

递归解题

那么按照上面给我们的数组，它的排序是根节点，左孩子，右孩子，那么我们就可以根据这个数组，先去递归到当前最深的左孩子或者右孩子，再通过递归往外获取它的节点值，获取到的这个顺序就是我们需要的后序遍历了。

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
 var postorder = function(root) {
    const ans = new Array()
    dfs = function(node) {
        if(node != null) {
            for(const child of node.children)
                dfs(child)
            ans.push(node.val)
        }
    }
    dfs(root)
    return ans
}
复制代码