20200615SolutionDeserializeNarryTree.java

/**
 * Time Complexity:     O(N)
 *  O(N), total number of N-arry tree nodes
 * 
 * Space Complexity:    O(W) + O(N)
 *  O(W), the maximum width of this N-arry tree
 *  O(N), consumed by the answer N-arry tree
 * 
 * 
 * Example 1: [1, null, 3, 2, 4, null, 5, 6]
 * 
 * Example 2: [1, null, 2, 3, 4, 5, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14]
 * 
 * Tree Visualization: 
 *  similar to LC0428. Serialize and Deserialize a N-arry Tree
 *  https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/
 */
package com.zea7ot.companies.other.construct_narry_tree_from_a_integer_array;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class SolutionApproach0BFS {
    public NarryTreeNode contructNarryTree(Integer[] nums){
        // sanity check
        if(nums == null || nums.length == 0 || nums[0] == null) return null;

        final int N = nums.length;
        Queue<NarryTreeNode> queue = new LinkedList<NarryTreeNode>();
        // to initialize idx with the first element, which might be "null",
        // of the first level, considering "root" level as level 0.
        int idx = 0;
        while(nums[idx] != null) idx++;
        idx++;

        NarryTreeNode root = new NarryTreeNode(nums[idx]);
        queue.offer(root);

        while(!queue.isEmpty()){
            final int SIZE = queue.size();

            for(int i = 0; i < SIZE; i++){
                NarryTreeNode parent = queue.poll();

                while(idx < N && nums[idx] != null){
                    NarryTreeNode child = new NarryTreeNode(nums[idx]);
                    parent.addChild(child);
                    queue.add(child);
                    idx++;
                }
            
                idx++;
            }
        }

        return root;
    }

    private class NarryTreeNode{
        @SuppressWarnings("unused")
        protected int val;
        protected List<NarryTreeNode> children;

        protected NarryTreeNode(int val){
            this.val = val;
            this.children = new ArrayList<NarryTreeNode>();
        }

        protected void addChild(NarryTreeNode child){
            this.children.add(child);
        }

        @SuppressWarnings("unused")
        protected void addChild(int val){
            this.children.add(new NarryTreeNode(val));
        }
    }
}