How do I get such a nested lists?

Question

variable tree structure

- nestedList1 variable

aa3
 |
aa1      aa2      bb1
   \    /        /
     aa       bb
       \     /
         root

- nestedList2 variable

              bb4
               |
aa3           bb2     bb3
 |              \     /
aa1      aa2      bb1    cc1
   \    /        /        |
     aa       bb         cc
       \       |        /
              root

nestedList1 = ['root', ['aa', ['aa1', ['aa3'], 'aa2'], 'bb', ['bb1']]]
nestedList2 = ['root', ['aa', ['aa1', ['aa3'], 'aa2'], 'bb', ['bb1', ['bb2', ['bb4'], 'bb3']], 'cc', ['cc1']]]

def ConvertTraverse(nlist, depth=0):
    convertlist = []
    for leaf in nlist:
        if isinstance(leaf, list):
            tmplist = ConvertTraverse(leaf, depth+1)
            convertlist.insert(0, tmplist)
        else:
            convertlist += [leaf]
    return convertlist

print ConvertTraverse(nestedList1)
print ConvertTraverse(nestedList2)

• result
  nestedList1: [[['bb1'], [['aa3'], 'aa1', 'aa2'], 'aa', 'bb'], 'root']
  nestedList2: [[['cc1'], [[['bb4'], 'bb2', 'bb3'], 'bb1'], [['aa3'], 'aa1', 'aa2'], 'aa', 'bb', 'cc'], 'root']

All I want is the results below.

• result
  nestedList1: [[[['aa3'], 'aa1', 'aa2'], 'aa', ['bb1'], 'bb'], 'root']
  nestedList2: [[[['aa3'], 'aa1', 'aa2'], 'aa', [[['bb4'], 'bb2', 'bb3'], 'bb1'], 'bb', ['cc1'], 'cc'], 'root']

How do I get such a nested list? I want a nested list, ordered to post-order traverse.

Answer 1

Basically, what you need to do in order to reorder the list: Whenever the nth element is a label, and the n+1th element is a sublist, swap the two. You can do this in-place in a few line:

def reorder(lst):
    for i, (cur, nxt) in enumerate(zip(lst, lst[1:])):
        if isinstance(cur, str) and isinstance(nxt, list):
            reorder(nxt)
            lst[i:i+2] = [nxt, cur]

For a not-in-place solution, you can just create a deep-copy of the list and then use that on the copy.