Рубрики

Самая длинная последовательная последовательность в двоичном дереве

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

Примеры:

In below diagram binary tree with longest consecutive path(LCP) are shown :


Мы можем решить вышеупомянутую проблему рекурсивно. На каждом узле нам нужна информация о его родительском узле, если текущий узел имеет значение на единицу больше, чем его родительский узел, то он делает последовательный путь, на каждом узле мы будем сравнивать значение узла с его родительским значением и соответственно обновлять самый длинный последовательный путь.
Для получения значения родительского узла мы передадим (node_value + 1) в качестве аргумента рекурсивному методу и сравним значение узла с этим значением аргумента, если оно удовлетворяет, обновим текущую длину последовательного пути, в противном случае повторно инициализируем текущую длину пути с помощью 1.
Пожалуйста, смотрите код ниже для лучшего понимания:

C ++

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

using namespace std;

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

   дочерний элемент и указатель на правый дочерний элемент * /

struct Node

{

    int data;

    Node *left, *right;

};

  
// Вспомогательная функция для создания узла

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

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

    return temp;

}

  
// Служебный метод для возврата длины самого длинного
// последовательная последовательность дерева

void longestConsecutiveUtil(Node* root, int curLength,

                              int expected, int& res)

{

    if (root == NULL)

        return;

  

    // если у корневых данных больше, чем у их родителя

    // затем увеличиваем текущую длину

    if (root->data == expected)

        curLength++;

    else

        curLength = 1;

  

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

    res = max(res, curLength);

  

    // рекурсивно вызываем левое и правое поддерево с

    // ожидаемое значение на 1 больше корневых данных

    longestConsecutiveUtil(root->left, curLength,

                           root->data + 1, res);

    longestConsecutiveUtil(root->right, curLength,

                           root->data + 1, res);

}

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

int longestConsecutive(Node* root)

{

    if (root == NULL)

        return 0;

  

    int res = 0;

  

    // вызов служебного метода с текущей длиной 0

    longestConsecutiveUtil(root, 0, root->data, res);

  

    return res;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    Node* root = newNode(6);

    root->right = newNode(9);

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

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

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

  

    printf("%d\n", longestConsecutive(root));

    return 0;

}

Джава

// Java программа для поиска самой длинной последовательности
// последовательность в двоичном дереве

  

class Node

{

    int data;

    Node left, right;

  

    Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class Result 

{

    int res = 0;

}

  

class BinaryTree

{

    Node root;

  

    // метод возвращает длину самого длинного подряд

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

    int longestConsecutive(Node root)

    {

        if (root == null)

            return 0;

  

        Result res = new Result();

          

        // вызов служебного метода с текущей длиной 0

        longestConsecutiveUtil(root, 0, root.data, res);

          

        return res.res;

    }

  

    // Служебный метод для возврата длины самого длинного

    // последовательная последовательность дерева

    private void longestConsecutiveUtil(Node root, int curlength, 

                                        int expected, Result res)

    {

        if (root == null)

            return;

  

        // если у корневых данных больше, чем у их родителя

        // затем увеличиваем текущую длину

        if (root.data == expected)

            curlength++;

        else

            curlength = 1;

  

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

        res.res = Math.max(res.res, curlength);

  

        // рекурсивно вызываем левое и правое поддерево с

        // ожидаемое значение на 1 больше корневых данных

        longestConsecutiveUtil(root.left, curlength, root.data + 1, res);

        longestConsecutiveUtil(root.right, curlength, root.data + 1, res);

    }

  

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

  

        tree.root = new Node(6);

        tree.root.right = new Node(9);

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

        tree.root.right.right = new Node(10);

        tree.root.right.right.right = new Node(11);

  

        System.out.println(tree.longestConsecutive(tree.root));

    }

}

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

python3

# Python3 программа для поиска самой длинной подряд
# последовательность в двоичном дереве

  
# Сервисный класс для создания узла

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = self.right = None

  
# Служебный метод для возврата длины
# самая длинная последовательная последовательность деревьев

def longestConsecutiveUtil(root, curLength, 

                           expected, res):

    if (root == None):

        return

  

    # если корневые данные имеют на одну больше, чем его

    # родитель, затем увеличьте текущую длину

    if (root.data == expected): 

        curLength += 1

    else:

        curLength = 1

  

    # обновить максимум по текущей длине

    res[0] = max(res[0], curLength)

  

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

    # с ожидаемым значением на 1 больше, чем корневые данные

    longestConsecutiveUtil(root.left, curLength, 

                           root.data + 1, res) 

    longestConsecutiveUtil(root.right, curLength,

                           root.data + 1, res)

  
# метод возвращает длину самого длинного подряд
# последовательность с корнем в корне узла

def longestConsecutive(root):

    if (root == None): 

        return 0

  

    res = [0]

  

    # вызов утилиты с текущей длиной 0

    longestConsecutiveUtil(root, 0, root.data, res) 

  

    return res[0]

  
Код водителя

if __name__ == '__main__':

  

    root = newNode(6

    root.right = newNode(9

    root.right.left = newNode(7

    root.right.right = newNode(10

    root.right.right.right = newNode(11

  

    print(longestConsecutive(root))

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

C #

// C # программа для поиска самой длинной последовательности
// последовательность в двоичном дереве

using System; 

class Node 

    public int data; 

    public Node left, right; 

  

    public Node(int item) 

    

        data = item; 

        left = right = null

    

  

class Result 

    public int res = 0; 

  

class GFG 

    Node root; 

  

    // метод возвращает длину самого длинного подряд

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

    int longestConsecutive(Node root) 

    

        if (root == null

            return 0; 

  

        Result res = new Result(); 

          

        // вызов служебного метода с текущей длиной 0

        longestConsecutiveUtil(root, 0, root.data, res); 

          

        return res.res; 

    

  

    // Служебный метод для возврата длины самого длинного

    // последовательная последовательность дерева

    private void longestConsecutiveUtil(Node root, int curlength, 

                                        int expected, Result res) 

    

        if (root == null

            return

  

        // если у корневых данных больше, чем у их родителя

        // затем увеличиваем текущую длину

        if (root.data == expected) 

            curlength++; 

        else

            curlength = 1; 

  

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

        res.res = Math.Max(res.res, curlength); 

  

        // рекурсивно вызываем левое и правое поддерево с

        // ожидаемое значение на 1 больше корневых данных

        longestConsecutiveUtil(root.left, curlength, 

                               root.data + 1, res); 

        longestConsecutiveUtil(root.right, curlength, 

                               root.data + 1, res); 

    

  

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

    public static void Main(String []args) 

    

        GFG tree = new GFG(); 

  

        tree.root = new Node(6); 

        tree.root.right = new Node(9); 

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

        tree.root.right.right = new Node(10); 

        tree.root.right.right.right = new Node(11); 

  

        Console.WriteLine(tree.longestConsecutive(tree.root)); 

    

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


Выход:

3

Также обсуждается по ссылке ниже:
Максимальное последовательное увеличение длины пути в двоичном дереве

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

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

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

Самая длинная последовательная последовательность в двоичном дереве

0.00 (0%) 0 votes