Question

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?

Solution:

  • Method 1: dfs 
    /*
// 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 {
    private List<Integer> result;
    public List<Integer> preorder(Node root) {
        this.result = new ArrayList<>();
        if(root == null) return result;
        dfs(root);
        return result;
    }
    private void dfs(Node node){
        if(node == null) return;
        result.add(node.val);
        for(int i = 0; i < node.children.size(); i++){
            dfs(node.children.get(i));
        }
    }
}
  • Method 2: Iteration
    • We need to use stack to implement this question.
    • For example: [1,3,5,6,2,4]
    • step 1: we push 1 to stack, stack: [1]
    • step 2: push its child to stack in reverse order. stack: [3, 2, 4]
    • step 3: take the first element from stack, and save all its children into stack using step 2, stack: [5, 6, 2, 4] 
      /*
// 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> result = new ArrayList<>();
      if(root == null) return result;
      Stack<Node> stack = new Stack<>();
      stack.push(root);
      while(!stack.isEmpty()){
          Node node = stack.pop();
          result.add(node.val);
          for(int i = node.children.size() - 1; i >= 0; i--){
              stack.push(node.children.get(i));
          }
      }
      return result;
  }
}

Reference

  1. Leetcode 589. N-ary Tree Preorder Traversal