Given an n-ary tree, return thepreordertraversal of its nodes' values.
For example, given a3-arytree:
Return its preorder traversal as:[1,3,5,6,2,4].
Note:
Recursive solution is trivial, could you do it iteratively?
Solution
// Definition for a Node.
/*
// 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;
}
};
*/
DFS - Recursive
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
preorderHelper(root, res);
return res;
}
private void preorderHelper(Node root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
for (Node node: root.children) {
preorderHelper(node, res);
}
}
}
DFS - Iterative
/*
// 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> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
res.add(node.val);
if (node.children != null) {
Collections.reverse(node.children);
for (Node c: node.children) {
stack.push(c);
}
}
}
return res;
}
}
