leetcode説明--589.N-ary Tree Preorder Traversal

タイトル

Given an n-ary tree, return the preorder traversal of its nodes' values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4] .
Note:
Recursive solution is trivial, could you do it iteratively?
タイトルアドレス

説明する

再帰的に問題を解くと、とても簡単です.反復で問題を解くなら、スタックで実現することにほかならない.注意すべき点は、スタックを押す順序を逆にするために追加のスタックが必要であることです.

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 preorder(Node root) {
        if(root==null){
            return result;
        }
        result.add(root.val);
        for(Node node:root.children){
            preorder(node);
        }
        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 preorder(Node root) {
        if(root==null){
            return result;
        }
        stack.push(root);
        while(!stack.empty()){
            Node theNode = stack.pop();
            result.add(theNode.val);
            for(Node node:theNode.children){
                stack_temp.push(node);
            }
            while(!stack_temp.empty()){
                stack.push(stack_temp.pop());
            }
        }
        return result;
    }
}