问题

给定一个 \(N\) 叉树，返回其节点值的前序遍历。
例如，给定一个 \(3叉树\) :
 

返回其前序遍历: \([1,3,5,6,2,4]\)。

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

解法

如果忽略说明的话，使用递归确实非常简单。与二叉树的前序遍历一样，唯一需要注意的一点是儿子是个list。递归转迭代也只是用栈来缓存
下面给出递归与迭代的不同代码

代码

java

递归方式

/*
// 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 LinkedList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        dfs(root);
        return result;
    }
    private void dfs(Node root) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        //唯一需要注意的就是这里的对儿子的处理
        if (root.children !=null) {
            for(Node node:root.children) {
                dfs(node);
            }
        }
    }
}

迭代方式

/*
// 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 LinkedList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        //使用栈来存储
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.val);
            if (node.children !=null) {
                List<Node> children = node.children;
                //这里需要注意的一点是，压栈的顺序，要从最右开始压
                for(int i=children.size() - 1;i >= 0;i--){
                    stack.push(children.get(i));
                }
            }
        }
        return result;
    }
}