递归获取二叉树中节点的路径

Question

我在获取二叉树中一个节点的路径时遇到了问题。具体来说，当我从堆栈框架返回时，我不知道如何从堆栈中弹出元素。

def getPath(self, target):

    stack = []

    def _getPath(head):
        nonlocal stack
        nonlocal target

        stack.append(head)

        if head.value == target:
            return stack
        if head.left is not None:
            _getPath(head.left)
        if head.right is not None:
            _getPath(head.right)

    _getPath(self.root)

    return stack

当前，堆栈将包含树中的所有元素。

Answer 1

这里的一个问题是:目标何时找到的信息必须传播回被调用的getPath实例。堆栈的构造是发现的一种“副作用”。因此，我建议您在getPath中返回一个布尔值，即在当前被调查的子树中找到目标的真当且仅当。然后，我们知道我们必须将一个值附加到“堆栈”：

def getPath(self, target):

    stack = []

    def _getPath(head):
        nonlocal stack
        nonlocal target
        if head.value == target:
            stack.append(head)
            return True
        for child in (head.left, head.right):
            if child is not None:
                if  _getPath(child):
                    stack.append(head)
                    return True
        return False


    _getPath(self.root)
    return reversed(stack)