递归调用时更改 Python 中的列表

Question

我正在 binary tree and I got stuck in the question Lowest Common Ancestor in a Binary Tree | Set 1.

上解决一些问题

我正在使用 Python 来解决问题。

我的问题是在我们想要找到 4 和 5 之间的共同祖先的情况下，如何在第一次调用函数时返回 [1,2,4]...

当 (root.right!= None 和 findPath(root.right, path, k) 被递归调用。

PS：请参考link

中给出的Python代码

Answer 1

您询问的代码似乎是 findPath 函数，复制于此：

# Finds the path from root node to given root of the tree.
# Stores the path in a list path[], returns true if path
# exists otherwise false
def findPath( root, path, k):
 
    # Baes Case
    if root is None:
        return False
 
    # Store this node is path vector. The node will be
    # removed if not in path from root to k
    path.append(root.key)
 
    # See if the k is same as root's key
    if root.key == k :
        return True
 
    # Check if k is found in left or right sub-tree
    if ((root.left != None and findPath(root.left, path, k)) or
            (root.right!= None and findPath(root.right, path, k))):
        return True
 
    # If not present in subtree rooted with root, remove
    # root from path and return False
      
    path.pop()
    return False

（来源：https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/）

而且您对 path 输出参数的工作原理感到困惑。这是一个公平的问题，因为该算法对于它如何构建该列表有点间接。

让我们看看所有 return 代码路径，并特别关注发生这种情况时 path 发生的情况。我把上面的代码复制了下来，没有注释，只关注函数的主要逻辑。评论是我的。我还将“root”重命名为“current”，因为这使方法更加清晰。

def findPath(current, path, k):
 
    # Put the current node's key at the end of the path list.
    path.append(current.key)
 
    # Return immediately if the current node is the target.
    if current.key == k:
        return True
 
    # Return immediately if one of the current node's children contains the target.
    if ((current.left != None and findPath(current.left, path, k)) or
            (current.right!= None and findPath(current.right, path, k))):
        return True
 
    # Remove the current node's key from the path list.
    path.pop()
    return False

因此，我们可以将此函数视为本质上执行以下操作（在伪代码中）：

def findPath(current, path, target):
  path += current.key
  if (current or its children contain target):
    return True
  else 
    path -= current.key
    return False

请注意，只有在“快乐”的情况下，当前或其子项包含目标，我们才会将 current.key 留在 path 中。在所有其他代码路径中，我们从 path 中删除 current.key。所以，最后，path 将恰好包含 root 和 target 之间的键。

递归调用时更改 Python 中的列表

Change in a list in Python when it is called recursively

python

binary-tree

data-structures