Flatten List Iterator

Question (LI.22)

Given a list of nestedInteger, flatten into a list of integers. Or equivalently, given a n-ary tree, find all the leaves in preorder.

Preorder Traversal

Step 1 Define recursion
flatten(List<Integer> result, List<NestedInteger> nestedList)
find all the leaves in preorder of this tree or nestedList

Step 2 Recursive calls
for (int i = 0; i < nestedList.size(); i++)
    if (!nestedList.get(i).isInteger())
        flatten(result, nestedList, i)
    else
        result.add(nestedList.get(i).getInteger())

Step 3 Base case
if leave add to result

public List<Integer> flatten(List<NestedInteger> nestedList) {
    List<Integer> result = new ArrayList<>();
    if (nestedList == null || nestedList.size() == 0) {
        return result;
    }
    flattenHelper(result, nestedList);
    return result;
}

private void flattenHelper(List<Integer> result, 
                           List<NestedInteger> nestedList) {
    for (int i = 0; i < nestedList.size(); i++) {
        if (!nestedList.get(i).isInteger()) {
            flattenHelper(result, nestedList.get(i).getList());
        } else {
            result.add(nestedList.get(i).getInteger());
        }
    }
}

Solve by Recursion

Step 1 Define Recursion
flatten(List<NestedInteger> nestedList) 
will return a list of integers that are the leaves of this tree

Step 2 Recursive calls
for all children
    if child.isInteger()
        result.add(child.getInteger())
    else
        result.addAll(flatten(child.getList))

Step 3 Base case
if child is integer
    add to result

public List<Integer> flatten(List<NestedInteger> nestedList) {
    List<Integer> result = new ArrayList<>();
    for (NestedInteger child : nestedList) {
        if (child.isInteger()) {
            result.add(child.getInteger());
        } else {
            result.addAll(flatten(child.getList()));
        }
    }
    return result;
}

Iterative BFS

Iterative layer by layer

// iterative approach
public List<Integer> flatten(List<NestedInteger> nestedList) {
    List<Integer> result = new ArrayList<>();
    if (nestedList == null || nestedList.size() == 0) {
        return result;
    }        
    // init first layer of BFS
    List<NestedInteger> layer = new ArrayList<>(nestedList);
    boolean notFlat = true;
    // iterative bfs
    while (notFlat) {
        List<NestedInteger> newLayer = new ArrayList<>();
        notFlat = false;
        for (NestedInteger child : layer) {
            if (child.isInteger()) {
                newLayer.add(child);
            } else {
                newLayer.addAll(child.getList());
                notFlat = true;
            }
        }
        layer = newLayer;
    }
    for (NestedInteger ele : layer) {
        result.add(ele.getInteger());
    }
    return result;
}