LeetCode题解之N叉树的后序遍历

N叉树的后序遍历

题目描述

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

**说明: **递归法很简单，你可以使用迭代法完成此题吗?

解题思路

使用两个链表来得到 N 叉树的后序遍历结果，其中一个链表作为辅助空间，一个链表用于存放后序遍历的结果。首先把根节点加入辅助链表。然后每次从辅助链表的尾部取出节点，加入到结果链表的头部，每次取出一个节点之后，就把该节点的所有子节点加入到辅助链表中去。这样就能确保结果链表中存储的就是 N 叉树的后序遍历结果了。

复杂度分析

• 时间复杂度：O(n)，其中 n 为树中节点的个数。
• 空间复杂度：O(n)，在最坏的情况下，N 叉树只有两层，这时候需要长度为 n - 1 的辅助空间来存储 N 叉树中的节点，因此空间复杂度为 O(n) 。

代码实现

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Node> helper = new LinkedList<>();
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        helper.add(root);
        while (!helper.isEmpty()) {
            Node node = helper.pollLast();
            res.addFirst(node.val);
            for (Node n : node.children) {
                helper.add(n);
            }
        }
        return res;
    }
}