LeetCode 590 N-ary Tree Postorder Traversal

题意

给定一颗 N 叉树 的根节点,返回后序遍历后的数组.

例 :

1
2
3
4
5
6
7
给予树:
1
/ | \
3 2 4
/ \
5 6
将其后序遍历返回: [5,6,3,2,4,1].

解法

和二叉树的中序遍历差不多,需要注意处理好子节点的顺序即可。

非递归解法:

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
/*
// 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 {
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<>();

if (root == null) {
return list;
}

Stack<Node> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
Node node = stack.peek();
List<Node> children = node.children;
if (children != null && children.size() != 0) {
for (int i = children.size() - 1; i >= 0; i--) {
stack.add(children.get(i));
}
} else {
list.add(stack.pop().val);
}
node.children = new ArrayList<>();
}

return list;
}
}

递归解法:

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
/*
// 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 {

List<Integer> list = new ArrayList<>();

public List<Integer> postorder(Node root) {
if (root == null) {
return list;
}

for (Node child : root.children) {
postorder(child);
}

list.add(root.val);

return list;
}
}

Runtime: 1 ms, faster than 100.00% of Java online submissions for N-ary Tree Postorder Traversal.
Memory Usage: 48.2 MB, less than 40.66% of Java online submissions for N-ary Tree Postorder Traversal.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-590/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!