问题

给定类BinarySearchTree，这是TAD二叉搜索树的实现，仅使用对每个节点的子节点的引用（_right、_left），我们被要求实现BinarySearchTree类的子类BST2，其中包括以下方法：

1. find_dist_k(self, n, k)。该方法接收两个参数n和k，它们都是正整数，将返回一个包含所有与元素n的节点距离为k的Python列表。两个节点之间的距离是必须遍历的链接数，不考虑链接的方向，即节点A和节点B之间的距离与节点B和节点A之间的距离相同。如果未在树中找到参数n，则该方法将返回一个空列表。

请注意，我们不能使用self.parent。

以下是经过一些研究后我获得的代码：

def find_dist_k(self, n: int, k: int) -> list:
    # 在这里写你的代码
    result = []
    node = self.search(n)
    if node is None:
        return result
    if n < 0 or k < 0:
        print("函数的参数必须是正数")
    self._find_dist_k(node, k, result)
    return result

def _find_dist_k(self, node, k, result):
    if node is None:
        return
    if k == 0:
        result.append(node.elem)
    else:
        self._find_dist_k(node.left, k - 1, result)
        self._find_dist_k(node.right, k - 1, result)

它工作得很好。但是，它只返回在元素下方的元素。看一下这个示例：
input_list_01 = [5, 12, 2, 1, 3, 9]
如果我执行这个函数self.find_dist_k(5, 2)，输出 = [1, 3, 9]
如果我执行这个函数self.find_dist_k(3, 2)，输出 = []，但它应该是[5]。

有什么评论来修复这个问题吗？

def find_dist_k(self, n: int, k: int) -> list:
    # Here your code
    result = []
    node = self.search(n)
    if node is None:
        return result
    if n < 0 or k < 0:
        print("parameters of the function must be positive")
    self._find_dist_k(node, k, result)
    return result

def _find_dist_k(self, node, k, result):
    if node is None:
        return
    if k == 0:
        result.append(node.elem)
    else:
        self._find_dist_k(node.left, k - 1, result)
        self._find_dist_k(node.right, k - 1, result)

答案1

得分: 1

以下是您提供的代码的中文翻译部分：

您所使用的示例树如下所示：

```none
         _5_
        /   \
       2     12
      / \   /
     1   3 9

当输入为节点3且k=2时，解决方案不仅应返回节点5，还应返回节点1，因为该节点也与节点3相隔2个边。

该算法应该回溯到它跟随到目标节点的路径，并保留还剩多少距离可用。因此，对于示例，它应该从节点3回溯到节点2，然后访问k=0的替代子树，因为已经经过2步到达替代子树（带有节点1）。

然后它应该再次回溯一步（从节点2到节点5），在那里发现剩余距离为0，应输出该节点。

这也意味着您不能使用self.search，因为该方法只返回目标节点，没有关于到该节点的路径的任何信息。相反，实现一个类似搜索的算法，但使用递归，这样调用者仍然可以使用父节点。然后当递归调用返回时，检查还剩多少距离可用，如果有的话，收集兄弟子树中该深度的节点。

注意：我没有看到您的BST实现如何调用根节点，但我将假设它具有_root属性。

以下是可能的实现：

def find_dist_k(self, n: int, k: int) -> list:
    result = []

    def collect_depth_k(node, k):
        if node:
            if k == 0:
                result.append(node.elem)
            elif k > 0:
                collect_depth_k(node.left, k - 1)
                collect_depth_k(node.right, k - 1)
    
    def recur_dist_k(node, k):
        if not node:  # 未找到n
            return -1
        if n == node.elem:
            # 找到节点：收集深度为k的所有后代节点
            collect_depth_k(node, k)
        else:
            # 尚未找到，继续搜索
            child, sibling = [node.left, node.right] if n < node.elem else [node.right, node.left]
            k = recur_dist_k(child, k)
            # 如果k < 0，那么要么未找到节点，要么我们距离它太远
            if k == 0: # 我们位于发现节点的正上方的正确距离
                result.append(node.elem)
            elif k > 0: # 检查另一个子树是否有剩余距离的子节点
                collect_depth_k(sibling, k - 1)
        return k - 1  # 返回父节点可用的剩余距离
    
    recur_dist_k(self._root, k)
    return result

请注意，这是代码的翻译部分，不包括问题的回答。如果您有其他问题或需要进一步的帮助，请随时提出。

<details>
<summary>英文:</summary>

The example tree you have used looks like this:

```none
         _5_
        /   \
       2     12
      / \   /
     1   3 9

When the input is node 3 with k=2, then not only should the solution return node 5, but also node 1 since that node is also 2 edges away from node 3.

The algorithm should trace back on the path it followed to the target node and retain how much distance is left to work with. So for the example, it should trace back from node 3 to node 2 and there visit the alternate subtree with k=0, since it already took 2 steps to get to the alternate subtree (with node 1).

Then it should trace back one step more (from node 2 to node 5), where it finds that the remaining distance is 0 and that node should be output.

This also means you cannot use self.search, as that method only returns the target node without any information about the path to that node. Instead implement a search-like algorithm, but use recursion, so the caller still has the parent node to work with. Then when the recursive call comes back, check how much distance is still available, and if any, collect the nodes at that depth in the sibling subtree.

NB: I didn't see how your BST implementation calls the root, but I will assume it has a _root attribute.

Here is a possible implementation:

    def find_dist_k(self, n: int, k: int) -> list:
        result = []

        def collect_depth_k(node, k):
            if node:
                if k == 0:
                    result.append(node.elem)
                elif k > 0:
                    collect_depth_k(node.left, k - 1)
                    collect_depth_k(node.right, k - 1)
        
        def recur_dist_k(node, k):
            if not node:  # n not found
                return -1
            if n == node.elem:
                # Found node: collect all descendants at depth k
                collect_depth_k(node, k)
            else:
                # Not yet found, continue search
                child, sibling = [node.left, node.right] if n < node.elem else [node.right, node.left]
                k = recur_dist_k(child, k)
                # If k < 0 then either the node was not found, or we are too far above it
                if k == 0: # we are at the right distance above the found node
                    result.append(node.elem)
                elif k > 0: # Check other subtree for children at remaining distance
                    collect_depth_k(sibling, k - 1)
            return k - 1  # Return how much distance is remaining for parent to work with
        
        recur_dist_k(self._root, k)
        return result

答案2

得分: 0

你正在获取输入节点以下的元素，因为你的递归引用了 node.left 和 node.right - 我假设它们是子元素。

为了考虑来自祖先节点的节点 - 你需要单独添加它们 -

def _find_dist_k(self, node, k, result):
    # ... 你的代码在这里
    current_node = node
    for i in range(k):
        current_node = current_node.parent
    if i == k:
        result.append(current_node)

def _find_dist_k(self, node, k, result):
    # ... Your code goes here
    current_node = node
    for i in range(k):
        current_node = current_node.parent
    if i == k:
        result.append(current_node)