items = [
    {"id": "1", "parent": ""},
    {"id": "2", "parent": "1"},
    {"id": "3", "parent": "1"},
    {"id": "4", "parent": ""},
    {"id": "5", "parent": "4"},
    {"id": "6", "parent": "4"},
    {"id": "7", "parent": "4"},
    {"id": "8", "parent": "2"},
    {"id": "9", "parent": "8"},
]
"""
利用python的引用特性
a = []
b = ['2']
c = ['3']

a.append(b)
b.append(c)
if __name__ == '__main__':
    print(a)
[['2', ['3']]]
"""


def flat2nested(datas):
    res = []
    tree = {item['id']: item for item in datas}
    for obj in datas:
        if not obj['parent']:
            root = tree[obj['id']]
            res.append(root)
        else:
            parent_id = obj['parent']
            if 'children' not in tree[parent_id]:
                tree[parent_id]['children'] = []
            tree[parent_id]['children'].append(tree[obj['id']])
    return res


if __name__ == '__main__':
    print(flat2nested(items))

"""
data = [
    {
        'id': '1',
        'parent': '',
        'children': [
            {
                'id': '2',
                'parent': '1',
                'children': [
                    {
                        'id': '8',
                        'parent': '2',
                        'children': [
                            {
                                'id': '9',
                                'parent': '8'
                            }
                        ]
                    }
                ]
            },
            {
                'id': '3',
                'parent': '1'
            }
        ]
    },
    {
        'id': '4',
        'parent': '',
        'children': [
            {
                'id': '5',
                'parent': '4'},
            {
                'id': '6',
                'parent': '4'},
            {
                'id': '7',
                'parent': '4'
            }
        ]
    }
]
"""