Рубрики

Проверьте, есть ли путь от корня к листу с заданной последовательностью

Для заданного двоичного дерева и массива задача состоит в том, чтобы найти, присутствует ли заданная последовательность массивов в виде пути от корня к листу в данном дереве.

Примеры :

Input : arr[] = {5, 2, 4, 8} for above tree
Output: "Path Exist"

Input :  arr[] = {5, 3, 4, 9} for above tree
Output: "Path does not Exist"

Простое решение этой проблемы — найти все пути от корня к листу в данном дереве, а для каждого пути от корня к листу проверить, что путь и заданная последовательность в массиве одинаковы или нет.

Эффективным решением этой проблемы является обход дерева один раз, и при обходе дерева мы должны убедиться, что путь от корневого до текущего узла идентичен заданной последовательности пути от корневого до конечного. Вот алгоритм:

  • Начните обход дерева по предварительному заказу .
  • Всякий раз, когда мы движемся вниз по дереву, мы также перемещаемся на один индекс в данной последовательности пути от корня к листу.
  • Если текущий узел равен arr [index], это означает, что до этого уровня путь дерева идентичен.
  • Теперь оставшийся путь будет либо в левом поддереве, либо в правом поддереве .
  • Если какой-либо узел не соответствует arr [index], это означает, что текущий путь не идентичен заданной последовательности пути от корня к листу, поэтому мы возвращаемся назад и перемещаемся в правильное поддерево.
  • Теперь, когда мы находимся на листовом узле, и он равен arr [index], и в данной последовательности пути от корня к листу больше нет элемента, это означает, что путь существует в данном дереве.
  • C ++

    // C ++ программа, чтобы увидеть, есть ли путь от корня к листу
    // с заданной последовательностью.
    #include<bits/stdc++.h>

    using namespace std;

      
    / * Узел двоичного дерева содержит данные, указатель на левого потомка
    и указатель на правого ребенка * /

    struct Node

    {

        int data;

        struct Node* left, *right;

    };

      
    / * утилита, которая выделяет новый узел с
    данные даны и NULL левый и правый указатели. * /

    struct Node* newnode(int data)

    {

        struct Node* node = new Node;

        node->data = data;

        node->left = node->right  = NULL;

        return (node);

    }

      
    // функция для проверки заданной последовательности пути от корня к листу
    // в дереве или нет.
    // индекс представляет текущий элемент в последовательности
    // листовой путь

    bool existPath(struct Node *root, int arr[], int n, int index)

    {

        // Если root равен NULL, тогда не должно быть никаких элементов

        // в массиве.

        if (root == NULL)

            return (n == 0);

      

       // Если этот узел является листом и соответствует последней записи

       // массива.

       if ((root->left == NULL && root->right == NULL) &&

           (root->data == arr[index]) && (index == n-1))

                return true;

      

       // Если текущий узел равен arr [index], это означает

       // что до этого уровня путь был найден и

       // оставшийся путь может быть либо в левом поддереве, либо

       // правильное поддерево.

       return ((index < n) && (root->data == arr[index]) &&

                  (existPath(root->left, arr, n,  index+1) ||

                   existPath(root->right, arr, n, index+1) ));

    }

      
    // Функция драйвера для запуска дела

    int main()

    {

        // arr [] -> последовательность пути от корня к листу

        int arr[] = {5, 8, 6, 7};

        int n = sizeof(arr)/sizeof(arr[0]);

        struct Node *root = newnode(5);

        root->left    = newnode(3);

        root->right   = newnode(8);

        root->left->left = newnode(2);

        root->left->right = newnode(4);

        root->left->left->left = newnode(1);

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

        root->right->left->right = newnode(7);

      

        existPath(root, arr, n, 0)? cout << "Path Exists" :

                                    cout << "Path does not Exist";

        return 0;

    }

    Джава

    // Java-программа, чтобы увидеть, есть ли путь от корня к листу
    // с заданной последовательностью.

    public class CheckForPath {

      

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

        // в дереве или нет.

        // индекс представляет текущий элемент в последовательности

        // листовой путь

        public static boolean existPath(Node root, int arr[], int index)

        {

            // Если root равен NULL, тогда не должно быть никаких элементов

            // в массиве.

            if(root==null)

            {

                return arr.length==0;

            }

      

            // Если этот узел является листом и соответствует последней записи

            // массива.

            if((root.left==null && root.right==null) && (root.data==arr[index] 

                                            && root.data==arr[arr.length-1]))

            {

                return true;

            }

      

            // Если текущий узел равен arr [index], это означает

            // что до этого уровня путь был найден и

            // оставшийся путь может быть либо в левом поддереве, либо

            // правильное поддерево.

            return (index<arr.length && (root.data==arr[index] && 

                   (existPath(root.left,arr,index+1) || 

                    existPath(root.right, arr, index+1))));

        }

      

        public static void main(String args[]) {

            // arr [] - последовательность пути от корня до листа

            int arr[] = {5, 8, 6, 7}; 

            Node root=new Node(5);

            root.left=new Node(3);

            root.right=new Node(8);

            root.left.left = new Node(2); 

            root.left.right = new Node(4); 

            root.left.left.left = new Node(1); 

            root.right.left = new Node(6); 

            root.right.left.right = new Node(7); 

      

            if(existPath(root, arr, 0))

            {

                System.out.print("Path Exists");

            }

            else

            {

                System.out.print("Path does not Exist");

            }

        }   

    }

      
    / * Узел двоичного дерева содержит данные, указатель на левого потомка
    и указатель на правого ребенка * /

    class Node 

        int data; 

        Node left, right; 

        Node(int data)

        {

            this.data=data;

            left=right=null;

        }

    }; 

      
    // Этот код предоставлен Гауравом Тивари

    python3

    # Python3 программа, чтобы увидеть, есть ли
    # путь от корня к листу с заданной последовательностью.

      
    # утилита, которая выделяет новый узел с
    # даны данные и нет левого и правого указателей.

    class newnode: 

        def __init__(self, data):

            self.data = data 

            self.left = self.right = None

      
    # функция для проверки заданной последовательности корня
    # путь к листу существует в дереве или нет.
    # index представляет текущий элемент в
    # последовательность пути от рута до листа

    def existPath(root, arr, n, index):

          

        # Если root - None, то должен

        # не быть элементом в массиве.

        if (root == None):

            return (n == 0)

      
    # Если этот узел является листом и соответствует
    # с последней записью массива.

        if ((root.left == None and root.right == None) and

            (root.data == arr[index]) and (index == n - 1)): 

            return True

      
    # Если текущий узел равен arr [index]
    # это означает, что до этого уровня пути
    # было найдено и оставшийся путь
    # может быть либо в левом поддереве, либо
    # правильное поддерево.

        return ((index < n) and (root.data == arr[index]) and 

                (existPath(root.left, arr, n, index + 1) or

                 existPath(root.right, arr, n, index + 1)))

      
    Код водителя

    if __name__ == '__main__':

          

        # arr [] -. последовательность пути от корня к листу

        arr = [5, 8, 6, 7

        n = len(arr) 

        root = newnode(5

        root.left = newnode(3

        root.right = newnode(8

        root.left.left = newnode(2

        root.left.right = newnode(4

        root.left.left.left = newnode(1

        root.right.left = newnode(6

        root.right.left.right = newnode(7

      

        if existPath(root, arr, n, 0):

            print("Path Exists"

        else:

            print("Path does not Exist")

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

    C #

    // C # программа, чтобы увидеть, если есть
    // путь от корня к листу
    // с заданной последовательностью.

    using System;

      

    public class CheckForPath 

    {

      

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

        // существует путь от корня к листу

        // в дереве или нет.

        // индекс представляет текущий элемент

        // в последовательности от Рута до

        // листовой путь

        public static bool existPath(Node root,

                            int []arr, int index)

        {

            // Если root равен NULL, тогда

            // не должно быть ни одного элемента

            // в массиве.

            if(root == null)

            {

                return arr.Length == 0;

            }

      

            // Если этот узел является листом и соответствует последней записи

            // массива.

            if((root.left == null && root.right == null) && 

                                    (root.data == arr[index] &&

                                    root.data == arr[arr.Length - 1]))

            {

                return true;

            }

      

            // Если текущий узел равен arr [index], это означает

            // что до этого уровня путь был найден и

            // оставшийся путь может быть либо в левом поддереве, либо

            // правильное поддерево.

            return (index < arr.Length && (root.data == arr[index] && 

                           (existPath(root.left,arr,index + 1) || 

                            existPath(root.right, arr, index + 1))));

        }

          

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

        public static void Main() 

        {

            // arr [] - последовательность пути от корня до листа

            int []arr = {5, 8, 6, 7}; 

            Node root=new Node(5);

            root.left=new Node(3);

            root.right=new Node(8);

            root.left.left = new Node(2); 

            root.left.right = new Node(4); 

            root.left.left.left = new Node(1); 

            root.right.left = new Node(6); 

            root.right.left.right = new Node(7); 

      

            if(existPath(root, arr, 0))

            {

                Console.Write("Path Exists");

            }

            else

            {

                Console.Write("Path does not Exist");

            }

        

    }

      
    / * Узел двоичного дерева содержит данные,
    указатель на левого ребенка и
    указатель на правого ребенка * /

    public class Node 

        public int data; 

        public Node left, right; 

        public Node(int data)

        {

            this.data = data;

            left = right = null;

        }

    };

      
    // Этот код предоставлен Rajput-Ji


    Выход:

Path Exists

Временная сложность: O (n)

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Проверьте, есть ли путь от корня к листу с заданной последовательностью

0.00 (0%) 0 votes