LeetCode/589. N叉树的前序遍历

589. N叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

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

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

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解：

既然是树的遍历，那么一共就是两种思路，即深度优先搜索遍历和广度优先搜索遍历。其中递归法就是深度优先搜索遍历的思想，我们从左到右依次遍历N叉树的每个节点。

具体代码如下：

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    List<Integer> result = new ArrayList<>();

    public List<Integer> preorder(Node root) {
        if (root == null) return result;
        result.add(root.val);
      	//遍历当前节点的所有孩子节点
        for (int i = 0; i < root.children.size(); i++) {
            preorder(root.children.get(i));
        }
        return result;
    }
}

题目要求思考迭代方法来遍历，能想到的就是借鉴广度优先搜索遍历的方法。创建一个栈，每次栈顶弹出的元素就是前序遍历的顺序。具体来说，逆序每个节点的孩子节点，然后依次入栈，每次pop()栈顶的元素，就是前序遍历的顺序。

具体代码如下：

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    List<Integer> result = new ArrayList<>();

    public List<Integer> preorder(Node root) {
        if (root == null) return result;
        Deque<Node> deque = new ArrayDeque<>();
        deque.add(root);

        while (!deque.isEmpty()) {
            Node node = deque.pop();
            result.add(node.val);
          	//每次逆序入栈当前节点的所有孩子节点
            Collections.reverse(node.children);
            for (Node child : node.children) {
                deque.push(child);
            }
        }

        return result;
    }
}