590. N 叉树的后序遍历

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

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

进阶：

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

示例 1：

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

解法一：递归解法   理解递归解法

 public List postorder(Node root) {         List res = new ArrayList();         postorder(root, res);         return res;     }
    void postorder(Node root,List res) {          if(root==null)              return ;         for(Node node:root.children) {             postorder(node,res);         }         res.add(root.val);             }

解法二：迭代求解

public List postorder(Node root) {
        LinkedList res = new LinkedList<>();
        if(root == null)
            return res;
        Deque stack = new ArrayDeque<>();
        stack.addLast(root);
        while(!stack.isEmpty()) {
            Node node = stack.removeLast();
            res.addFirst(node.val);
            for(int i=0;i) {
                stack.addLast(node.children.get(i));
            }
        }
        return res;
    }

解法三：很秀的一种解法

更为简洁的写法。这种解法的思想是先序遍历的变形，先序遍历是“根->左->右”，后序遍历是“左->右->根”，那么把先序遍历改成“根->右->左”，再逆序一下就是后序遍历。

既然递归转迭代是必然的，那么每次我们转换的时候，该怎么转，依然是一大难题

 

LeetCode题集

相关

标签