leetcode 590. N叉树的后序遍历

题目描述

给定一个 N 叉树，返回其节点值的后序遍历。
相关话题： 树    难度： 简单

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单，你可以使用迭代法完成此题吗?

• 解法1
  使用递归的方法先遍历当前节点的所有children节点，遍历完后处理当前节点。

    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    public void postorder(Node root, List<Integer> res){
        if(root == null) return;
        //遍历当前节点的children
        for(Node x : root.children){
            postorder(x, res); 
        }
        //遍历完children后，处理当前节点
         res.add(root.val);
    }

• 解法2
  迭代方式的解题思路和leetcode 145题类似，同样用到两个栈，一个协助以“中->右->左”遍历树，一个保存遍历的结果。
• 初始状态下，stack1保存了根节点(为了统一操作，包装到list)。
• while循环内，弹出stack1中的List对象（也就是子节点的集合），先处理最后一个节点(Node x = list.remove(list.size()-1);stack2.push(x);)，然后如果list不为空的话，将其压回到stack1中，并将当前节点(最右的节点)的子节点集合压到stack1中。
• stack1为空时，遍历结束。
  以上就是“中->右->左”的遍历过程。

public List<Integer> postorder(Node root) {
        if(root == null) return new ArrayList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        //保存剩余未遍历子节点(左)
        Stack<List<Node>> stack1 = new Stack<>();
        //保存结果
        Stack<Node> stack2 = new Stack<>();
        List<Node> tmp = new ArrayList<Node>();
        tmp.add(root);
        stack1.push(tmp);
        while(!stack1.isEmpty()){
            List<Node> list = stack1.pop();
            Node x = list.remove(list.size()-1);
            stack2.push(x);
            if(!list.isEmpty()){
                stack1.push(list);
            }
            if(!x.children.isEmpty()){
                stack1.push(x.children);
            }
        }
        while(!stack2.isEmpty()){
            res.add(stack2.pop().val);
        }
        return res;
    }