Рубрики

K-й предок узла в двоичном дереве | Набор 3

Дано двоичное дерево, в котором узлы пронумерованы от 1 до N. Даны узел и положительное целое число K. Мы должны напечатать K- го предка данного узла в двоичном дереве. Если такого предка не существует, выведите -1 .

Например, в приведенном ниже двоичном дереве 2- й предок узлов 4 и 5 равен 1 . 3- й предок узла 4 будет -1 .

Подход: сначала мы находим путь заданных ключевых данных из корня и сохраняем их в векторе, затем просто возвращаем k- й индекс вектора из последнего.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Структура дерева

struct node {

    node *left, *right;

    int data;

};

  
// Создать новый узел

node* newNode(int data)

{

    node* temp = new node;

    temp->left = temp->right = NULL;

    temp->data = data;

    return temp;

}

  
// Функция для поиска пути от
// корень к целевому узлу

bool RootToNode(node* root, int key, vector<int>& v)

{

    if (root == NULL)

        return false;

  

    // Добавить текущий узел в путь

    v.push_back(root->data);

  

    // Если текущий узел является целевым узлом

    if (root->data == key)

        return true;

  

    // Если целевой узел существует в

    // левое или правое поддерево

    if (RootToNode(root->left, key, v)

        || RootToNode(root->right, key, v))

        return true;

  

    // Удалить последний вставленный узел как

    // это не часть пути

    // от корня до цели

    v.pop_back();

    return false;

}

  
// Код драйвера

int main()

{

    struct node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

  

    // данный узел

    int target = 4;

  

    // Вектор для хранения пути от

    // корень данного узла

    vector<int> v;

  

    // Находим путь от корня до целевого узла

    RootToNode(root, target, v);

  

    int k = 2;

  

    // Распечатать Kth предка

    if (k > v.size() - 1 || k <= 0)

        cout << -1;

    else

        cout << v[v.size() - 1 - k];

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

  
// Структура дерева

static class node

{

    node left, right;

    int data;

};

  
// Создать новый узел

static node newNode(int data)

{

    node temp = new node();

    temp.left = temp.right = null;

    temp.data = data;

    return temp;

}

  
// Функция для поиска пути от
// корень к целевому узлу

static boolean RootToNode(node root, int key,

                            Vector<Integer> v)

{

    if (root == null)

        return false;

  

    // Добавить текущий узел в путь

    v.add(root.data);

  

    // Если текущий узел является целевым узлом

    if (root.data == key)

        return true;

  

    // Если целевой узел существует в

    // левое или правое поддерево

    if (RootToNode(root.left, key, v)

        || RootToNode(root.right, key, v))

        return true;

  

    // Удалить последний вставленный узел как

    // это не часть пути

    // от корня до цели

    v.removeElementAt(v.size()-1);

    return false;

}

  
// Код драйвера

public static void main(String[] args) 

{

    node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(6);

    root.right.right = newNode(7);

  

    // данный узел

    int target = 4;

  

    // Вектор для хранения пути от

    // корень данного узла

    Vector<Integer> v = new Vector<>();

  

    // Находим путь от корня до целевого узла

    RootToNode(root, target, v);

  

    int k = 2;

  

    // Распечатать Kth предка

    if (k > v.size() - 1 || k <= 0)

        System.out.println(-1);

    else

        System.out.println(v.get(v.size() - 1 - k));

}
}

  
// Этот код предоставлен Принчи Сингхом

python3

# Python3 реализация подхода

  
# Создать узел

class Node:

   

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Функция для поиска пути
# от корня до целевого узла

def RootToNode(root, key, v): 

   

    if root == None

        return False 

  

    # Добавить текущий узел в путь

    v.append(root.data) 

  

    # Если текущий узел является целевым узлом

    if root.data == key: 

        return True 

  

    # Если целевой узел существует в

    # левое или правое поддерево

    if (RootToNode(root.left, key, v) or

       RootToNode(root.right, key, v)):

        return True 

  

    # Удалить последний вставленный узел

    # поскольку это не является частью

    # путь от корня до цели

    v.pop() 

    return False 

   
# Код драйвера

if __name__ == "__main__"

   

    root = Node(1

    root.left = Node(2

    root.right = Node(3

    root.left.left = Node(4

    root.left.right = Node(5

    root.right.left = Node(6

    root.right.right = Node(7

  

    # Данный узел

    target, k = 4, 2 

  

    # Вектор для хранения пути

    # от корня до данного узла

    v = [] 

  

    # Найти путь от корня до целевого узла

    RootToNode(root, target, v) 

  

    # Распечатать Kth предка

    if k > len(v) - 1 or k <= 0

        print(-1

    else:

        print(v[len(v) - 1 - k]) 

  
# Этот код предоставлен Rituraj Jain

C #

// C # реализация вышеуказанного подхода

using System.Collections.Generic;

using System;

  

class GFG

{

  
// Структура дерева

public class node

{

    public node left, right;

    public int data;

};

  
// Создать новый узел

static node newNode(int data)

{

    node temp = new node();

    temp.left = temp.right = null;

    temp.data = data;

    return temp;

}

  
// Функция для поиска пути от
// корень к целевому узлу

static bool RootToNode(node root, int key,

                            List<int> v)

{

    if (root == null)

        return false;

  

    // Добавить текущий узел в путь

    v.Add(root.data);

  

    // Если текущий узел является целевым узлом

    if (root.data == key)

        return true;

  

    // Если целевой узел существует в

    // левое или правое поддерево

    if (RootToNode(root.left, key, v)

        || RootToNode(root.right, key, v))

        return true;

  

    // Удалить последний вставленный узел как

    // это не часть пути

    // от корня до цели

    v.Remove(v.Count-1);

    return false;

}

  
// Код драйвера

public static void Main(String[] args) 

{

    node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(6);

    root.right.right = newNode(7);

  

    // данный узел

    int target = 4;

  

    // Вектор для хранения пути от

    // корень данного узла

    List<int> v = new List<int>();

  

    // Находим путь от корня до целевого узла

    RootToNode(root, target, v);

  

    int k = 2;

  

    // Распечатать Kth предка

    if (k > v.Count - 1 || k <= 0)

        Console.WriteLine(-1);

    else

        Console.WriteLine(v[v.Count - 1 - k]);

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

1

Рекомендуемые посты:

K-й предок узла в двоичном дереве | Набор 3

0.00 (0%) 0 votes