algorithm - 打印距离 BST 中给定节点 'x' 处的所有节点

Question

详细问题是找到距离给定节点x(即边数=x)的所有节点。

我今天在亚马逊面试中被问到，

void findNodeWithDistanceX(struct node* root,struct node * qnode, int value)
{
    //root is root Node, qnode is questionnode from which distance to be calculated, value is the            
    //distance to be calculated


    //finding distance between root and qnode
    int distance = findDistancefromRoot(root ,qnode);

    if(distance> value)
    {
        traverseDistancedown(root ,distance-value);
    }

    if(distance ==value){
        printf("%d",root->value);
    }

    // Traverse and find all nodes with distance value from 'qnode' down the tree
    traverseDistancedown(qnode,value);

现在如果找到与 qnode 的距离“值”。
我没有得到答案如何向上遍历树并满足距离有值的条件。

虽然这里出现了很多情况。

我尝试从 qnode 回溯，但无济于事，我无法打动他，也无法编写代码。

任何关于实现树上遍历的讨论都会对我有所帮助。

Answer 1

最简单的方法是深度优先搜索，在搜索过程中跟踪距离。这是从“问题节点”开始的简单预序遍历。

void nodesAtDistance(struct node* qnode, int requestedDistance, int currentDistance)
{
    if (qnode == null) return;

    if (currentDistance == requestedDistance)
    {
        // output qnode
        // and then return because children are further away
        return;
    }

    // visit left and then right
    nodesAtDistance(qnode->left, requestedDistance, currentDistance+1);
    nodesAtDistance(qnode->right, requestedDistance, currentDistance+1);
}

所以如果你调用它:

nodesAtDistance(myNode, 5, 0);

它将输出myNode以下5层的所有节点。

现在，如果我将其编写为 API 函数，我将提供一个重载，它不需要客户端传递 currentDistance 参数。因为如果有人要写 nodesAtDistance(myNode, 5, 1)，你会在距离 4 处得到东西。所以，创建这个重载:

void nodesAtDistance(node * qnode, int requestedDistance)
{
    nodesAtDistance(qnode, requestedDistance, 0);
}

使该函数公开可见，并将另一个函数设为私有(private)。