时间戳

首页 > 解决方案 > 在二叉树中寻找较低的祖先

python - 在二叉树中寻找较低的祖先

问题描述

我想在二叉树中找到较低的祖先，我要做的是首先列出每个节点的父亲，然后比较列表，最后一个共同点是较低的祖先。

我有这个代码：

def ancesters(self, node, list= []):
    if self.seekNode(node) != False:
        if node < self.id:
            list.append(self.id)
            return self.left.ancesters(node)
        elif node > self.id:
            list.append(self.id)
            return self.right.ancesters(node)
        elif self.id == node:
            list.append(self.id)
            return list
    else:
        return False

函数 seekNode 工作，这个方法也可以，但是当我使用该方法两次时，显示最后一次调用的祖先列表，例如：

我有这棵树：

               2
               |
                ---
                   5
                  ---
                 3   6

当我调用方法 ancesters(6) 时，列表将是 (2,5,6)，当我再次调用搜索 3 的父亲时，显示 (2,5,6,2,5,3)。

那么，当我设置参数（list=[]）时，为什么列表没有初始化并保存列表值？我用相同的对象调用该方法，在这种情况下将是树的节点（根）。节点是树的节点（根）的实例。

标签： pythonrecursiontree

解决方案

简而言之，不要使用可变对象（如列表）作为默认值。这是Anti-Pattern，因为在 Python 中，默认值在所有函数调用之间共享。所以它必须是不可变的。流行的选项是无和条件if not None: ...

你也可以在这里阅读

推荐阅读