589. N 叉树的前序遍历——迭代法实现

力扣题目链接——N叉树的前序遍历。

---

题目

给定n叉树的根节点root，返回其节点值的前序遍历。

n叉树再输入中按照层序遍历进行序列化表示，每一组子节点都是由空值null区分。请见下图：

---

思路 迭代法

利用栈模拟递归，较为难处理的是当前节点u的子节点v1返回时，需要处理节点u的下一个节点v2，需记录当前已经遍历完那些节点，才可以找到下一个需要遍历的节点。

• 首先用Java的List集合存储res结果数组，判定是否空，空则直接返回。
• 利用Stack，将root节点压入栈。
• 利用while循环，若栈非空，则开始处理左右子节点。
• 另root等于栈的pop数值。
• 将root.val结果加入res集合中。
• 利用List假定Node的孩子节点，并另其等于root.children。
• 调用Java的Collections.reverse方法，反转输出children集合的元素。
• forEach遍历集合元素，若不空则将结果添加到res集合结果中。

代码展示

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

    public Node() {}

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

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

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            res.add(root.val);
            List<Node> children = root.children;
            Collections.reverse(children);
            for (Node each: children) {
                if (each != null) {
                    stack.push(each);
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Java的Collections工具类

Collections 提供了如下方法用于对 List 集合元素进行排序。

• reverse(List list)：对指定的List集合进行逆向排序。
• shuffle：对指定的List集合进行随机排序，模拟洗牌行为。
• sort：根据元素的自然顺序对指定的List集合元素按照升序进行排序。
• sort(List list, Comparator c)： 根据指定的Comparator产生的顺序对List集合进行排序。
• swap(List list, int i, init j)：将指定的List集合的i索引元素和j索引元素进行交换。

给出demo程序如下，实现循环录入 5 个商品的名称，并按录入时间的先后顺序进行降序排序，即后录入的先输出：

public class Test2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        List students = new ArrayList();
        System.out.println("******** 商品信息 ********");
        for (int i = 0; i < 5; i++) {
            System.out.println("请输入第 " + (i + 1) + " 个商品的名称：");
            String name = input.next();
            students.add(name); // 将录入的商品名称存到List集合中
        }
        Collections.reverse(students); // 调用reverse()方法对集合元素进行反转排序
        System.out.println("按录入时间的先后顺序进行降序排列为：");
        for (int i = 0; i < 5; i++) {
            System.out.print(students.get(i) + "\t");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17