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

Question

我在获取二叉树中节点的路径时遇到问题。具体来说，我不知道如何将元素从堆栈中弹出，因为我 return 从堆栈帧中弹出元素。

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 的调用实例。堆栈的构造有点像 "side effect" 的发现。因此，我向您建议 return getPath 中的布尔值，如果目标是在当前调查的子树中找到的，则该值为 True。然后我们知道我们必须附加一个值到 "stack":

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)

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

Recursively obtaining path to node in binary tree

python

recursion

binary-tree