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ではなく、2回目にアクセスしたのはpopです.

Javaコード

再帰解法:

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

    public Node() {}

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

反復解法:

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

    public Node() {}

    public Node(int _val,List _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List result = new 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;
        }
    }
}