LeetCode 589 - N-ary Tree Preorder Traversal

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;
    }

https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/277302/Java-iterative-and-recursive

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

1. iterative solution idea is same as Binary tree.
2. as it is satck, we need push element in stack from last to 0 index. like in binary tree righ then left.
3. 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;
        
    }