algorithm - 在具有超过 2 个子节点的树上进行深度优先搜索

Question

我正在努力准备面试，但遇到了这个问题：

给定树结构的根。getChildren() 方法返回 Node[] 数组，其中包含该父项的所有子项。问题是检查给定节点 x 是否存在于树中。我将如何以迭代和递归的方式执行此操作？有人可以为它提供伪代码会有所帮助。我知道我们可以进行深度优先搜索，但我不确定如何为每个元素可以有任意数量的子节点的树执行此操作。

Answer 1

您的递归方法可能如下所示

FUNCTION exists(Node target, Node root):

    Node[] children = root.getChildren()

    IF children NOT null:  //if there are children go on to visit each one
        FOR child IN children:
            IF exists(target,child):
                RETURN true
    ELSE: //the base case, when 'root' has no children check if it's the value
        RETURN root.value == target

    RETURN false //will only be reached from the first call to exists() if there hasn't been a match already

在 Python 中，这看起来像：

def exists(target,root):
    if isinstance(root,list):
        for child in root:
            if exists(target,child):
                return True
    else:
        return target == root
    return False

一些例子：

print exists(2,[[[2]]])
print exists(2,[[1,4,5,[2]]])
print exists(2,[0,0,0,[0,[1,1,1]]])
>>> 
True
True
False

python中的迭代将是

def existsNR(value,root):
    visitstack = [child for child in root]
    while visitstack:
        node = visitstack.pop()
        if isinstance(node,list):
            visitstack += node
        else:
            if node == value:
                return True
    return False 

这背后的逻辑是，您检查“root”的每个初始子项，对于每个有子项的子项，然后将子项推入堆栈并删除这些子项（子项）的“父项”。检查这些是否有孩子并以类似的方式添加它们......直到你到达一个没有孩子的地方，此时你检查是否相等。