Рубрики

Длина пути с максимальным количеством изгибов

По заданному бинарному дереву найдите длину пути с максимальным количеством изгибов.
Примечание. Здесь изгиб указывает переключение слева направо или наоборот при перемещении по дереву.
Например, рассмотрим пути ниже (L означает движение влево, R означает движение вправо):
LLRRRR — 1 изгиб
RLLLRR — 2 изгиба
ЛРЛЛРР — 5 изгибов

Предварительное условие: определение максимальной длины пути в двоичном дереве

Примеры:

Input : 
            4
          /   \
        2      6
      /  \    / \
    1     3  5   7
                /
               9
              / \
             12 10
                  \
                  11
                  / \
                45  13
                      \
                      14

Output : 6
In the above example, the path 4-> 6-> 7-> 9-> 10-> 11-> 45
is having the maximum number of bends, i.e., 3. 
The length of this path is 6. 

Подходить :
Идея состоит в том, чтобы пройти по дереву для левого и правого поддеревьев корня. Во время перемещения следите за направлением движения (влево или вправо). Всякий раз, когда направление движения изменяется слева направо или наоборот, увеличивайте количество изгибов в текущем пути на 1.
Достигнув конечного узла, сравните число изгибов в текущем пути с максимальным количеством изгибов (т. Е. MaxBends), замеченных до сих пор в пути от корня к листу. Если количество изгибов в текущем пути больше, чем maxBends, то обновите maxBends, равное количеству изгибов в текущем пути, и обновите максимальную длину пути (то есть, len) также до длины текущего пути.

Реализация :

C ++

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

using namespace std;

  
// узел структуры

struct Node {

    int key;

    struct Node* left;

    struct Node* right;

};

  
// Сервисная функция для создания нового узла

struct Node* newNode(int key)

{

    struct Node* node = new Node();

    node->left = NULL;

    node->right = NULL;

    node->key = key;

  

    return node;

}

  
/ * Рекурсивная функция для расчета пути
длина, имеющая максимальное количество изгибов.
Ниже приведены параметры для этой функции.

  
узел -> указатель на текущий узел
dir -> определяет, является ли текущий узел
левый или правый потомок его родительского узла
изгибы -> количество изгибов до сих пор в
текущий путь
maxBends -> максимальное количество изгибов в
путь от корня до листа
soFar -> длина текущего пути, так
далеко пройденный
len -> длина пути, имеющая максимум
количество изгибов
* /

void findMaxBendsUtil(struct Node* node,

                      char dir, int bends,

                      int* maxBends, int soFar,

                      int* len)

{

    // Базовый вариант

    if (node == NULL)

        return;

  

    // Конечный узел

    if (node->left == NULL && node->right == NULL) {

        if (bends > *maxBends) {

            *maxBends = bends;

            *len = soFar;

        }

    }

    // Повторяется как для левого, так и для правого ребенка

    else {

        if (dir == 'l') {

            findMaxBendsUtil(node->left, dir,

                             bends, maxBends,

                             soFar + 1, len);

            findMaxBendsUtil(node->right, 'r',

                             bends + 1, maxBends,

                             soFar + 1, len);

        }

        else {

            findMaxBendsUtil(node->right, dir,

                             bends, maxBends,

                             soFar + 1, len);

            findMaxBendsUtil(node->left, 'l',

                             bends + 1, maxBends,

                             soFar + 1, len);

        }

    }

}

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

int findMaxBends(struct Node* node)

{

    if (node == NULL)

        return 0;

  

    int len = 0, bends = 0, maxBends = -1;

  

    // Вызов левого поддерева корня

    if (node->left)

        findMaxBendsUtil(node->left, 'l',

                         bends, &maxBends, 1, &len);

  

    // Вызываем правое поддерево корня

    if (node->right)

        findMaxBendsUtil(node->right, 'r', bends,

                         &maxBends, 1, &len);

  

    // Включаем также корневой узел в длину пути

    len++;

  

    return len;

}

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

int main()

{

    / * Построенное двоичное дерево

      10

      / /

     8 2

    ///

    3 5 2

          /

           1

          /

         9

    * /

  

    struct Node* root = newNode(10);

    root->left = newNode(8);

    root->right = newNode(2);

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

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

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

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

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

  

    cout << findMaxBends(root) - 1;

  

    return 0;

}

python3

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

  
# Сервисная функция для создания нового узла

class newNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.key = key 

  
# Рекурсивная функция для расчета пути
# Длина с максимальным количеством изгибов.
# Ниже приведены параметры для этой функции.

      
# узел -. указатель на текущий узел
# Dir -. определяет, является ли текущий узел
# является левым или правым потомком своего родительского узла
# изгибы -. количество изгибов до сих пор в
# текущий путь.
# maxBends -. максимальное количество изгибов в
# путь от корня до листа
# слишком далеко -. Длина текущего пути, так
# далеко пройденный
# Лен -. Максимальная длина пути
# количество изгибов

  

def findMaxBendsUtil(node, Dir, bends, 

                     maxBends, soFar, Len):

                           

    # Базовый вариант

    if (node == None): 

        return

  

    # Конечный узел

    if (node.left == None and 

        node.right == None):

        if (bends > maxBends[0]): 

            maxBends[0] = bends 

            Len[0] = soFar

                               

    # Наличие левого и правого ребенка

    else:

        if (Dir == 'l'):

            findMaxBendsUtil(node.left, Dir, bends, 

                             maxBends, soFar + 1, Len

            findMaxBendsUtil(node.right, 'r', bends + 1

                             maxBends, soFar + 1, Len)

        else:

            findMaxBendsUtil(node.right, Dir, bends, 

                             maxBends, soFar + 1, Len

            findMaxBendsUtil(node.left, 'l', bends + 1

                             maxBends, soFar + 1, Len)

  
# Вспомогательная функция для вызова findMaxBendsUtil ()

def findMaxBends(node):

    if (node == None): 

        return 0

  

    Len = [0]

    bends = 0

    maxBends = [-1

  

    # Вызовите левое поддерево корня

    if (node.left):

        findMaxBendsUtil(node.left, 'l', bends,

                         maxBends, 1, Len

  

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

    if (node.right):

        findMaxBendsUtil(node.right, 'r', bends, 

                         maxBends, 1, Len

  

    # Включите также корневой узел

    # в пути Длина

    Len[0] += 1

  

    return Len[0]

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

if __name__ == '__main__':

      

    # Построенное двоичное дерево

    № 10

    # / /

    № 8 2

    # / / /

    # 3 5 2

    # /

    № 1

    # /

    № 9

    root = newNode(10

    root.left = newNode(8

    root.right = newNode(2

    root.left.left = newNode(3

    root.left.right = newNode(5

    root.right.left = newNode(2

    root.right.left.right = newNode(1

    root.right.left.right.left = newNode(9

  

    print(findMaxBends(root) - 1)

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


Выход:

4

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

Длина пути с максимальным количеством изгибов

0.00 (0%) 0 votes