python 动态对象查询

Question

我有一个 python 对象，结构如下:

tree = {
    "a": {
        "aa": {
            "aaa": {},
            "aab": {},
            "aac": {}
        },
        "ab": {
            "aba": {},
            "abb": {}
        }
    },
    "b": {
        "ba": {}
    },
    "c": {}
}

以及一组字符串列表，例如:

arr_1 = ["a", "ab"]
arr_2 = ["b", "ab"]
arr_3 = ["a", "ab", "aba"]

每个列表都定义了树中键的路径，我想确定该列表是否描述了穿过树的有效路径。

目前我可以实现逐个案例的答案，如下所示:

tree[arr_1[0]][arr_1[1]] # Returns correct object
tree[arr_2[0]][arr_2[1]] # Returns error
tree[arr_3[0]][arr_3[1]][arr_3[2]] # Returns correct object

虽然这不能满足我的要求。我更喜欢一个函数，它可以在树中搜索任何给定列表中的键。

以下函数几乎是我想要的，但它不处理不同长度的列表。

def is_valid(tree, arr):
    obj = tree[arr[0]][arr[1]]
    if len(obj) > 0:
        return(obj)
    else:
        return("No obj")

当前该函数输出

is_valid(tree, arr_1) # Returns the correct result
is_valid(tree, arr_2) # Returns an error
is_valid(tree, arr_3) # Returns the same result as arr_1, which is incorrect

任何人都可以帮助我扩展此函数以动态响应 arr 参数的长度吗？

谢谢!

Answer 1

我认为最简单的方法是利用递归。每个子树都是一棵树，每个子路径都是一条路径，因此我们可以查看路径中的第一个元素是否有效，然后从那里继续。

def is_valid(tree, path):

    # base case. Any path would be valid for any tree
    if len(path) == 0:
        return True

    # the path must be invalid, no matter what comes before or after
    if not path[0] in tree:
        return False

    # look at the rest
    return is_valid(tree[path[0]], path[1:])

如果您想要路径描述的子树，您可以这样做:

def is_valid(tree, path):

    if len(path) == 0:
        return tree # the only difference
    if not path[0] in tree:
        return False
    return is_valid(tree[path[0]], path[1:])