589. N-ary Tree Preorder Traversal
Last updated
Last updated
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> resultList = new LinkedList();
if(root == null) {
return resultList;
}
preorder(root, resultList);
return resultList;
}
private void preorder(Node node, List<Integer> resultList) {
if(node == null) {
return;
}
resultList.add(node.val);
if(node.children == null) {
return;
}
for(Node child: node.children) {
preorder(child, resultList);
}
}
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public List<Integer> preorder(Node root) {
LinkedList<Node> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
output.add(node.val);
Collections.reverse(node.children);
for (Node item : node.children) {
stack.add(item);
}
}
return output;
}
}