LeetCode 589 N-ary Tree Preorder Traversal

题意

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

例 :

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

解法

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

非递归解法:

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
/*
// 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> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}

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

while (!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
for (int i = root.children.size() - 1; i >= 0; i--) {
stack.add(root.children.get(i));
}
}
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
/*
// 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> preorder(Node root) {
if (root == null) {
return list;
}

list.add(root.val);
for (Node child : root.children) {
preorder(child);
}

return list;
}
}

Runtime: 1 ms, faster than 100.00% of Java online submissions for N-ary Tree Preorder Traversal.

Memory Usage: 47.9 MB, less than 51.19% of Java online submissions for N-ary Tree Preorder Traversal.

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