LeetCode590-N叉树的后序遍历

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/n-ary-tree-postorder-traversal/

中文链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

题目详述

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

例如，给定一个 3叉树 :

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

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

题目详解

类似于 LeetCode145-二叉树中的后序遍历，本题是N叉树的后序遍历。思路是一致的。

方法一：递归。

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
public class LeetCode_00590 {

    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(Node root, List<Integer> res) {
        if (root == null) {
            return;
        }
        for (Node child : root.children) {
            dfs(child, res);
        }
        res.add(root.val);
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

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

方法二：迭代。

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
public class LeetCode_00590 {

    public List<Integer> postorder(Node root) {
//        List<Integer> res = new ArrayList<>();
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(0, node.val);
            for (Node child : node.children) {
                stack.push(child);
            }
        }
        return res;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

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