DFS 遍历 JSON

题目：

输入一个多层JSON串，需要把嵌套的key通过英文字符 ’.’ 连接作为目标key，如果value不是对象则视为目标value，输出由目标key和目标value形成的单层字典。

思路：

其实题目本身没什么实际意义，只是考察树的dfs，创建一个栈，通过记录路径和判断是不是叶子节点，如果不是则继续往下找，如果是则保存路径和叶子节点。


import json


def solution(data):
    try:
        data_ = json.loads(data)  # 解析JSON串，异常则视为空字典
		except:
        data_ = dict()
    res = dict()  # 保存单层字典
    path = []  # 记录路径

    if not data_:  # 如果为空，直接返回空字典
        return res

    def dfs(data):
        if not isinstance(data, dict):  # 如果值不是字典，则保存路径和值，并结束这层递归
            res['.'.join(path)] = data
            return
        else:
            for k, v in data.items():  # 如果值是字典，则遍历字典，每层进行路径增加、进入递归、路径删除
                path.append(k)
                dfs(v)
                path.pop()

    dfs(data_) # 传入多层字典，开始递归
    return res


if __name__ == '__main__':
    data = '{"a1":{"b1":{"c1":1},"b2":{"c2":2}},"a2":{"b3":{"c3":3}}}'
    assert solution(data) == {'a1.b1.c1': 1, 'a1.b2.c2': 2, 'a2.b3.c3': 3}