Flatten List

Given a list, each element in the list can be a list or integer. flatten it into a simply list with integers.

Notice

If the element in the given list is a list, it can contain list too.

Example

Given [1,2,[1,2]], return [1,2,1,2].

Given [4,[3,[2,[1]]]], return [4,3,2,1].

Runtime: 441ms.

 1 /**
 2  * // This is the interface that allows for creating nested lists.
 3  * // You should not implement it, or speculate about its implementation
 4  * class NestedInteger {
 5  *   public:
 6  *     // Return true if this NestedInteger holds a single integer,
 7  *     // rather than a nested list.
 8  *     bool isInteger() const;
 9  *
10  *     // Return the single integer that this NestedInteger holds,
11  *     // if it holds a single integer
12  *     // The result is undefined if this NestedInteger holds a nested list
13  *     int getInteger() const;
14  *
15  *     // Return the nested list that this NestedInteger holds,
16  *     // if it holds a nested list
17  *     // The result is undefined if this NestedInteger holds a single integer
18  *     const vector<NestedInteger> &getList() const;
19  * };
20  */
21 class Solution {
22 public:
23     // @param nestedList a list of NestedInteger
24     // @return a list of integer
25     vector<int> flatten(vector<NestedInteger> &nestedList) {
26         // Write your code here
27         vector<int> result;
28         helper(nestedList, result);
29         return result;
30     }
31     
32     void helper(vector<NestedInteger> nestedList, vector<int>& result) {
33         for (int i = 0; i < nestedList.size(); i++) {
34             if (nestedList[i].isInteger()) 
35                 result.push_back(nestedList[i].getInteger());
36             else {
37                 helper(nestedList[i].getList(), result);
38             }
39         }
40     }
41 };