589. N-ary Tree Preorder Traversal

Description

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Constraints

The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The height of the n-ary tree is less than or equal to 1000.

Approach

Examples

Input: root = [1, null, 3, 2, 4, null, 5, 6]

Output: [1, 3, 5, 6, 2, 4]

Solutions

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

Follow up

Previous583. Delete Operation for Two Strings Next601-700

Last updated 4 years ago

Was this helpful?