https://leetcode.com/problems/n-ary-tree-preorder-traversal/
Given an n-ary tree, return the preorder traversal of its nodes' values.
For example, given a
3-ary tree:
Return its preorder traversal as:
[1,3,5,6,2,4].
Note:
Recursive solution is trivial, could you do it iteratively?
https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/147955/Java-Iterative-and-Recursive-Solutions 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.empty()) {
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;
}
}
Recursive Solution
class Solution {
public List<Integer> list = new ArrayList<>();
public List<Integer> preorder(Node root) {
if (root == null)
return list;
list.add(root.val);
for(Node node: root.children)
preorder(node);
return list;
}
List<Integer> res = new ArrayList<>(); public List<Integer> preorder(Node root) { preorderHelper(root); return res; } public void preorderHelper(Node root) { if (root == null) { return; } int val = root.val; res.add(val); List<Node> childs = root.children; for (int i = 0; i < childs.size(); i++) { preorderHelper(childs.get(i)); } } public List<Integer> preorder(Node root) { Stack<Node> stack = new Stack<>(); stack.push(root); List<Integer> res = new ArrayList<>(); if (root == null) { return res; } while (!stack.isEmpty()) { Node curr = stack.pop(); res.add(curr.val); List<Node> childs = curr.children; int size = childs.size() - 1; while (!childs.isEmpty()) { stack.add(childs.remove(size)); size--; } } return res; }https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/169079/Java-Time-O(N)-and-space-O(N)-recursive-iterative-solution-using-helper-method
- iterative solution idea is same as Binary tree.
- as it is satck, we need push element in stack from last to 0 index. like in binary tree righ then left.
- for more details - https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/168807/Java-O(N)-solution-recursion-and-using-loop-with-explanation
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
return helper(root, result);
}
private static List<Integer> helper(Node root, List<Integer> result) {
if(root != null){
result.add(root.val);
for(Node child : root.children){
helper(child, result);
}
}
return result;
}
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while(! stack.isEmpty()){
Node current = stack.pop();
result.add(current.val);
for(int i = current.children.size() -1 ; i >=0 ; i--){
stack.push(current.children.get(i));
}
}
return result;
}