给定一颗 N 叉树
的根节点,返回前序遍历后的数组.
例 :
给予树:
1
/ | \
3 2 4
/ \
5 6
将其前序遍历返回: [1,3,5,6,2,4].
和二叉树的前序遍历差不多,需要注意处理好子节点的顺序即可。
非递归解法:
/*
// 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;
}
}
递归解法:
/*
// 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.