leetcode讲解--590. N-ary Tree Postorder Traversal_Node.js

上一篇: node.js资源分享下一篇:Node.js+koa2

leetcode讲解--590. N-ary Tree Postorder Traversal

发布时间：2019-07-17 发布网站：脚本宝典

脚本宝典收集整理的这篇文章主要介绍了leetcode讲解--590. N-ary Tree Postorder Traversal，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目
Given an n-ary tree, return the postorder traversal of its nodes' values.
For example, given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].
Note:
Recursive solution is trivial, could you do it iteratively?
题目地址
讲解
这道题跟先序遍历差不多，调换一下添加结点的顺序而已。参考：leetcode讲解--589. N-ary Tree Preorder Traversal
但这道题的迭代解法稍微有点麻烦，需要一个标记，初次访问一个结点的时候我们并不能立即将它的值加进结果里，而是要等它的所有孩子访问完毕再加。也就是说我们第一次访问它并不pop，第二次访问它才pop。
Java代码
递归解法：

      
      
      ArrayList<>();
    public List postorder(Node root) {
        if(root==null){
            return result;
        }
        for(Node node:root.children){
            postorder(node);
        }
        result.add(root.val);
        return result;
    }
}" title="" data-original-title="复制">
      
      
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new ArrayList<>();
    public List<Integer> postorder(Node root) {
        if(root==null){
            return result;
        }
        for(Node node:root.children){
            postorder(node);
        }
        result.add(root.val);
        return result;
    }
}
迭代解法：

      
      
      ArrayList<>();
    private Stack stack = new Stack<>();
    private Stack stack_temp = new Stack();
    public List postorder(Node root) {
        if(root==null){
            return result;
        }
        Bundle rootBundle = new Bundle(root);
        stack.push(rootBundle);
        while(!stack.empty()){
            Bundle bundle = stack.peek();
            if(bundle.flag){
                result.add(stack.pop().node.val);
                continue;
            }
            for(Node node:bundle.node.children){
                Bundle d = new Bundle(node);
                stack_temp.push(d);
            }
            while(!stack_temp.empty()){
                stack.push(stack_temp.pop());
            }
            bundle.flag = true;
        }
        return result;
    }
    
    class Bundle{
        Node node;
        Boolean flag;
        public Bundle(Node node){
            flag = false;
            this.node = node;
        }
    }
}" title="" data-original-title="复制">
      
      
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new ArrayList<>();
    private Stack<Bundle> stack = new Stack<>();
    private Stack<Bundle> stack_temp = new Stack();
    public List<Integer> postorder(Node root) {
        if(root==null){
            return result;
        }
        Bundle rootBundle = new Bundle(root);
        stack.push(rootBundle);
        while(!stack.empty()){
            Bundle bundle = stack.peek();
            if(bundle.flag){
                result.add(stack.pop().node.val);
                continue;
            }
            for(Node node:bundle.node.children){
                Bundle d = new Bundle(node);
                stack_temp.push(d);
            }
            while(!stack_temp.empty()){
                stack.push(stack_temp.pop());
            }
            bundle.flag = true;
        }
        return result;
    }
    
    class Bundle{
        Node node;
        Boolean flag;
        public Bundle(Node node){
            flag = false;
            this.node = node;
        }
    }
}