Analysis:
{1, {2,3}, {4,{5,6},7}
/ | \
1 {2,3} {4,{5,6},
/ \ / \
2 3 4 {5,6}
/ \
5 6
Note, there are two types of nodes. One is actual number, the other is a list
As shown above, the problem can be solved by pre order traverse the tree. Simply, we can record the current index of a sub list to know which element should be visited.
class ListNode { public: std::vector<ListNode*> v; int val; //curIndex points the element to visit in v, if v is not empty //else curIndex == 0 means val is not visited yet. int curIndex; bool hasNext(){ if(!v.empty()) { if(curIndex >= v.size()) return false; if(!v[curIndex]->hasNext() && curIndex+1 >= v.size()) { return false; } return true; } //if the element is visited, curIndex is 1. return curIndex == 0; } int getNext(){ if(!v.empty()) { if(!v[curIndex]->hasNext()) curIndex++; return v[curIndex]->getNext(); } curIndex++; return val; } ListNode(int p){ curIndex = 0; val = p; } }; int main() { ListNode l0(-11), l2(-11), l3(-11), l32(-11); ListNode n1(1),n2(2), n3(3),n4(4), n5(5),n6(6),n7(7); l32.v.push_back(&n5); l32.v.push_back(&n6); l3.v.push_back(&n4); l3.v.push_back(&l32); l3.v.push_back(&n7); l2.v.push_back(&n2); l2.v.push_back(&n3); l0.v.push_back(&n1); l0.v.push_back(&l2); l0.v.push_back(&l3); while(l0.hasNext()) { std::cout << l0.getNext() << "\n"; } }