Узлы на расстоянии k в двоичном дереве

Question

Вам предоставляется функция printKDistanceNodes, которая принимает корневой узел двоичного дерева, начальный узел и целое число K. Завершите функцию, чтобы вывести значение всех узлов (по одному на строку), которые являются Kрасстояние от данного начального узла в отсортированном порядке.Расстояние может быть вверх или вниз.

Answer 1

private void printNodeAtN(Node root, Node start, int k) {
    if (root != null) {
        // calculate if the start is in left or right subtree - if start is
        // root this variable is null
        Boolean left = isLeft(root, start);
        int depth = depth(root, start, 0);

        if (depth == -1)
            return;
        printNodeDown(root, k);

        if (root == start)
            return;

        if (left) {
            if (depth > k) {
                // print the nodes at depth-k level in left tree
                printNode(depth - k - 1, root.left);
            } else if (depth < k) {
                // print the nodes at right tree level k-depth
                printNode(k - depth - 1, root.right);
            } else {
                System.out.println(root.data);
            }
        } else {
            // similar if the start is in right subtree
            if (depth > k) {
                // print the nodes at depth-k level in left tree
                printNode(depth - k - 1, root.right);
            } else if (depth < k) {
                // print the nodes at right tree level k-depth
                printNode(k - depth - 1, root.left);
            } else {
                System.out.println(root.data);
            }
        }
    }
}

    // print the nodes at depth - "level" from root
void printNode(int level, Node root) {
    if (level == 0 && root != null) {
        System.out.println(root.data);
    } else {
        printNode(level - 1, root.left);
        printNode(level - 1, root.right);
    }

}

// print the children of the start
void printNodeDown(Node start, int k) {
    if (start != null) {
        if (k == 0) {
            System.out.println(start.data);
        }
        printNodeDown(start.left, k - 1);
        printNodeDown(start.right, k - 1);
    }
}

private int depth(Node root, Node node, int d) {
    if (root == null)
        return -1;
    if (root != null && node == root) {
        return d;
    } else {
        int left = depth(root.left, node, d + 1);
        int right = depth(root.right, node, d + 1);
        if (left > right)
            return left;
        else
            return right;
    }
}

Answer 2

На расстоянии K находится не более одного узла, который вверх - просто начните с начального узла и двигайтесь вверх по родителям для K шагов. Добавьте это в отсортированную структуру данных.

Тогда вам нужно добавить нисходящие узлы. Для этого вы можете создать BFS с очередью, где вы сохраняете глубину вместе с узлом, когда вставляете его в очередь (начальный узел находится на уровне 0, это дочерние элементы на уровне 1 и т. Д.). Затем, когда вы выскальзываете узлы, если они находятся на уровне K, добавьте их в отсортированную структуру данных. когда вы начинаете вставлять узлы на уровне K + 1, вы можете остановиться.

Наконец, выведите узлы из отсортированной структуры данных (они будут отсортированы).

РЕДАКТИРОВАТЬ: если родительский указатель отсутствует:

Напишите рекурсивную функцию int Go(Node node), которая возвращает глубину начального узла относительно переданного узла и -1, если поддерево узла не содержит начала. Функция найдет K-го родителя в качестве побочного эффекта. Псевдокод:

static Node KthParent = null;
static Node start = ...;
static int K = ...;

int Go(Node node) {
    if (node == start) return 0;

    intDepth = -1;

    if(node.LeftChild != null) {
        int leftDepth = Go(node.LeftChild);
        if(leftDepth >= 0) intDepth = leftDepth+1;
    }
    if (intDepth < 0 && node.rightChild != null) {
        int rightDepth = Go(node.RightChild);
        if(rightDepth >= 0) intDepth = rightDepth+1;
    }

    if(intDepth == K) KthParent = node;

    return intDepth;
}

Answer 3

Вот полная программа Java.Вдохновленный алгоритмом geeksforgeeks

// Java program to print all nodes at a distance k from given node

class BinaryTreePrintKDistance {
 Node root;

    /*
     * Recursive function to print all the nodes at distance k in tree (or
     * subtree) rooted with given root.
     */

    void printKDistanceForDescendant(Node targetNode, int currentDist,
            int inputDist) {
        // Base Case
        if (targetNode == null || currentDist > inputDist)
            return;

        // If we reach a k distant node, print it
        if (currentDist == inputDist) {
            System.out.print(targetNode.data);
            System.out.println("");
            return;
        }

        ++currentDist;
        // Recur for left and right subtrees
        printKDistanceForDescendant(targetNode.left, currentDist, inputDist);
        printKDistanceForDescendant(targetNode.right, currentDist, inputDist);
    }

    public int printkdistance(Node targetNode, Node currentNode,
            int inputDist) {

        if (currentNode == null) {
            return -1;
        }

        if (targetNode.data == currentNode.data) {
            printKDistanceForDescendant(currentNode, 0, inputDist);
            return 0;
        }

        int ld = printkdistance(targetNode, currentNode.left, inputDist);

        if (ld != -1) {

            if (ld + 1 == inputDist) {
                System.out.println(currentNode.data);

            } else {
                printKDistanceForDescendant(currentNode.right, 0, inputDist
                        - ld - 2);
            }

            return ld + 1;
        }

        int rd = printkdistance(targetNode, currentNode.right, inputDist);

        if (rd != -1) {

            if (rd + 1 == inputDist) {
                System.out.println(currentNode.data);

            } else {
                printKDistanceForDescendant(currentNode.left, 0, inputDist - rd
                        - 2);
            }

            return rd + 1;
        }

        return -1;

    }

    // Driver program to test the above functions
    @SuppressWarnings("unchecked")
    public static void main(String args[]) {
        BinaryTreePrintKDistance tree = new BinaryTreePrintKDistance();

        /* Let us construct the tree shown in above diagram */
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);
        Node target = tree.root.left;

        tree.printkdistance(target, tree.root, 2);
    }

    static class Node<T> {
        public Node left;
        public Node right;
        public T data;

        Node(T data) {
            this.data = data;
        }
    }

}

Answer 4

Здесь в этом коде PrintNodesAtKDistance сначала попытается найти нужный узел.

if(root.value == requiredNode)

Когда мы находим нужный узел, мы печатаем все дочерние узлы на расстоянии K от этого узла.

Теперь наша задача - напечатать все узлы, которые находятся в других ветвяхи печать).Мы возвращаем -1, пока не нашли нужный нам узел.Получив нужный нам узел, мы получим lPath или rPath >=0.Теперь мы должны напечатать все узлы, которые находятся на расстоянии (lPath/rPath) -1

public void PrintNodes(Node Root, int requiredNode, int iDistance)

    {
        PrintNodesAtKDistance(Root, requiredNode, iDistance);
    }

    public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
    {
        if ((root == null) || (iDistance < 0))
            return -1;

        int lPath = -1, rPath = -1;

        if(root.value == requiredNode)
        {
            PrintChildNodes(root, iDistance);
            return iDistance - 1;
        }

        lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
        rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);

        if (lPath > 0)
        {
            PrintChildNodes(root.right, lPath - 1);
            return lPath - 1;
        }
        else if(lPath == 0)
        {
            Debug.WriteLine(root.value);
        }

        if(rPath > 0)
        {
            PrintChildNodes(root.left, rPath - 1);
            return rPath - 1;
        }
        else if (rPath == 0)
        {
            Debug.WriteLine(root.value);
        }

        return -1;
    }

    public void PrintChildNodes(Node aNode, int iDistance)
    {
        if (aNode == null)
            return;

        if(iDistance == 0)
        {
            Debug.WriteLine(aNode.value);
        }

        PrintChildNodes(aNode.left, iDistance - 1);
        PrintChildNodes(aNode.right, iDistance - 1);
    }

Answer 5

struct node{
       int data;
       node* left;
       node* right;
       bool printed;
};

void print_k_dist(node** root,node** p,int k,int kmax);
void reinit_printed(node **root);


void print_k_dist(node** root,node **p,int k,int kmax)
{
     if(*p==NULL) return;
     node* par=parent(root,p);
     if(k<=kmax &&(*p)->printed==0)
     {
             cout<<(*p)->data<<" ";
             (*p)->printed=1;
             k++;
             print_k_dist(root,&par,k,kmax);
             print_k_dist(root,&(*p)->left,k,kmax);
             print_k_dist(root,&(*p)->right,k,kmax);
     }
     else
         return;
}



void reinit_printed(node **root)
{
     if(*root==NULL) return;
     else
     {
         (*root)->printed=0;
         reinit_printed(&(*root)->left);
         reinit_printed(&(*root)->right);
     }
}          

Answer 6

typedef struct node
{
    int data;
    struct node *left;
    struct node *right;

}node;

void printkdistanceNodeDown(node *n, int k)
{
     if(!n)
       return ;

     if(k==0)
     {
        printf("%d\n",n->data);
        return;
     }

     printkdistanceNodeDown(n->left,k-1);
     printkdistanceNodeDown(n->right,k-1);   
}

void  printkdistanceNodeDown_fromUp(node* target ,int *k)
{   
    if(!target)
      return ;

      if(*k==0)
      {
         printf("%d\n",target->data); 
         return;
      }  
      else
      {
          int val=*k;
          printkdistanceNodeDown(target,val-1);
      }   
}

int printkdistanceNodeUp(node* root, node* n , int k)
{
    if(!root)
      return 0;

    if(root->data==n->data)
      return 1;

    int pl=printkdistanceNodeUp(root->left,n,k);      
    int pr=printkdistanceNodeUp(root->right,n,k);

     if(pl )
     {
      k--;

       if(k==0)
        printf("%d\n",root->data);
       else
      {
        printkdistanceNodeDown_fromUp(root->right,k);
        printkdistanceNodeDown_fromUp(root->left,k-1);
      }
       return 1;
    }

    if(pr )
    {
       k--;
      if(k==0)
        printf("%d\n",root->data);
      else
        { 
         printkdistanceNodeDown_fromUp(root->left,k);
         printkdistanceNodeDown_fromUp(root->right,k-1);
        }

       return 1;
    }

     return 0;
}

void printkdistanceNode(node* root, node* n , int k )
{
    if(!root)
      return ;

     int val=k;
     printkdistanceNodeUp(root,n,k);
     printkdistanceNodeDown(n,val);     

}

функция вызова: printkdistanceNode(root,n,k);

Выходные данные будут печатать все узлы на расстоянии k от заданного узла вверх и вниз.

Answer 7

private static int printNodeAtK(Node root, Node start, int k, boolean found){
        if(root != null){
            if(k == 0 && found){
                System.out.println(root.data);
            }
            if(root==start || found == true){
                int leftd = printNodeAtK(root.left, start, k-1, true);
                int rightd = printNodeAtK(root.right,start,k-1,true);
                return 1;
            }else{
                int leftd = printNodeAtK(root.left, start, k, false);
                int rightd = printNodeAtK(root.right,start,k,false);
                if(leftd == k || rightd == k){
                    System.out.println(root.data);
                }
                if(leftd != -1 && leftd > rightd){
                    return leftd+1;
                }else if(rightd != -1 && rightd>leftd){
                    return rightd+1;
                }else{
                    return -1;
                }
            }

        }
        return -1;
    }