Рубрики

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

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

       10
      /    \     
     /      \
    11        9    
   / \        /\
  /   \      /  \
13    12    13   8
Maximum Consecutive Path Length is 3 (10, 11, 12)
Note: 10, 9 ,8 is NOT considered since
the nodes should be in increasing order.

        5
          /  \
         /    \
        8      11
        /        \
       /          \
       9      10   
      /              /
     /             /
    6           15
Maximum Consecutive Path Length is 2 (8, 9).

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

prev : хранит значение родительского узла. Инициализируйте prev с одним значением меньше корневого узла, чтобы путь, начинающийся с root, имел длину не менее 1.
len : Сохраняет длину пути, которая заканчивается у родителя текущего посещенного узла.

Случай 1 : значение текущего узла ранее +1
В этом случае увеличьте длину пути на 1, а затем рекурсивно найдите длину пути для левого и правого поддерева, а затем верните максимум между двумя длинами.

Случай 2 : значение текущего узла НЕ предваряется + 1
Новый путь может начинаться с этого узла, поэтому рекурсивно найдите длину пути для левого и правого поддерева. Путь, который заканчивается в родительском узле текущего узла, может быть больше, чем путь, который начинается с этого узла. Таким образом, взять максимум пути, который начинается с этого узла и который заканчивается на предыдущем узле.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска максимально последовательных
// Длина пути в двоичном дереве
#include <iostream>

using namespace std;

  
// Представлять узел двоичного дерева

struct Node

{

    Node *left, *right;

    int val;

};

  
// Создать новый узел и вернуть его адрес

Node *newNode(int val)

{

    Node *temp = new Node();

    temp->val = val;

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

    return temp;

}

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

int maxPathLenUtil(Node *root, int prev_val, int prev_len)

{

    if (!root)

        return prev_len;

  

    // Получить значение Current Node

    // Значение текущего узла будет

    // предыдущий узел для его левого и правого детей

    int cur_val = root->val;

  

    // Если текущий узел должен быть частью

    // последовательный путь, тогда он должен быть на 1 больше

    // чем значение предыдущего узла

    if (cur_val == prev_val+1)

    {

  

        // а) Найти длину левого пути

        // б) Найти длину правильного пути

        // Возвращаем максимум левого пути и правого пути

        return max(maxPathLenUtil(root->left, cur_val, prev_len+1),

                   maxPathLenUtil(root->right, cur_val, prev_len+1));

    }

  

    // Находим длину максимального пути под поддеревом с этим

    // узел (путь может включать или не включать этот узел)

    int newPathLen = max(maxPathLenUtil(root->left, cur_val, 1),

                         maxPathLenUtil(root->right, cur_val, 1));

  

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

    // с этим узлом.

    return  max(prev_len, newPathLen);

}

  
// Оболочка над maxPathLenUtil ().

int maxConsecutivePathLength(Node *root)

{

    // Возвращаем 0, если root равен NULL

    if (root == NULL)

        return 0;

  

    // Остальное вычисляем максимальный последовательный путь увеличения

    // Длина с использованием maxPathLenUtil.

    return maxPathLenUtil(root, root->val-1, 0);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    Node *root = newNode(10);

    root->left = newNode(11);

    root->right = newNode(9);

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

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

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

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

  

    cout << "Maximum Consecutive Increasing Path Length is "

         << maxConsecutivePathLength(root);

  

    return 0;

}

Джава

// Java-программа для поиска максимально последовательных
// Длина пути в двоичном дереве

import java.util.*;

class GfG {

  
// Представлять узел двоичного дерева

static class Node 

    Node left, right; 

    int val; 

}

  
// Создать новый узел и вернуть его адрес

static Node newNode(int val) 

    Node temp = new Node(); 

    temp.val = val; 

    temp.left = null;

    temp.right = null

    return temp; 

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

static int maxPathLenUtil(Node root, int prev_val, int prev_len) 

    if (root == null

        return prev_len; 

  

    // Получить значение Current Node

    // Значение текущего узла будет

    // предыдущий узел для его левого и правого детей

    int cur_val = root.val; 

  

    // Если текущий узел должен быть частью

    // последовательный путь, тогда он должен быть на 1 больше

    // чем значение предыдущего узла

    if (cur_val == prev_val+1

    

  

        // а) Найти длину левого пути

        // б) Найти длину правильного пути

        // Возвращаем максимум левого пути и правого пути

        return Math.max(maxPathLenUtil(root.left, cur_val, prev_len+1), 

                maxPathLenUtil(root.right, cur_val, prev_len+1)); 

    

  

    // Находим длину максимального пути под поддеревом с этим

    // узел (путь может включать или не включать этот узел)

    int newPathLen = Math.max(maxPathLenUtil(root.left, cur_val, 1), 

                        maxPathLenUtil(root.right, cur_val, 1)); 

  

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

    // с этим узлом.

    return Math.max(prev_len, newPathLen); 

  
// Оболочка над maxPathLenUtil ().

static int maxConsecutivePathLength(Node root) 

    // Возвращаем 0, если root равен NULL

    if (root == null

        return 0

  

    // Остальное вычисляем максимальный последовательный путь увеличения

    // Длина с использованием maxPathLenUtil.

    return maxPathLenUtil(root, root.val-1, 0); 

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args) 

    Node root = newNode(10); 

    root.left = newNode(11); 

    root.right = newNode(9); 

    root.left.left = newNode(13); 

    root.left.right = newNode(12); 

    root.right.left = newNode(13); 

    root.right.right = newNode(8); 

  

    System.out.println("Maximum Consecutive Increasing Path Length is "+maxConsecutivePathLength(root)); 

  

питон

# Программа Python для поиска максимально последовательных
# длина пути в двоичном дереве

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, val):

        self.val = val 

        self.left = None

        self.right = None

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

def maxPathLenUtil(root, prev_val, prev_len):

    if root is None:

        return prev_len 

  

    # Получить информацию о текущем узле

    # Значение текущего узла будет

    # предыдущий узел для его левого и правого потомков

    curr_val =  root.val

      

    # Если текущий узел должен быть частью

    # последовательный путь, то он должен быть на 1 больше

    # thn значение предыдущего узла

    if curr_val == prev_val +1 :

          

        # а) Найдите длину левого пути

        # б) Найдите длину правильного пути

        # Вернуть максимум левого и правого пути

        return max(maxPathLenUtil(root.left, curr_val, prev_len+1), 

                   maxPathLenUtil(root.right, curr_val, prev_len+1))

  

    # Найти длину максимального пути под поддеревом

    # root с этим узлом

    newPathLen = max(maxPathLenUtil(root.left, curr_val, 1),

                    maxPathLenUtil(root.right, curr_val, 1))

  

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

    # root с этим узлом

    return max(prev_len , newPathLen)

  
# Обёртка над maxPathLenUtil ()

def maxConsecutivePathLength(root):

      

    # Вернуть 0, если root отсутствует

    if root is None:

        return 0 

      

    # Иначе вычислить максимальный последовательный путь увеличения

    # длина с использованием maxPathLenUtil

    return maxPathLenUtil(root, root.val -1 , 0)

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(10)

root.left = Node(11)

root.right = Node(9)

root.left.left = Node(13)

root.left.right = Node(12)

root.right.left = Node(13)

root.right.right = Node(8)

  

print "Maximum Consecutive Increasing Path Length is"

print maxConsecutivePathLength(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # Программа для поиска максимально последовательных
// Длина пути в двоичном дереве

using System;

  

class GfG 

{

  

    // Представлять узел двоичного дерева

    class Node 

    

        public Node left, right; 

        public int val; 

    }

  

    // Создать новый узел и вернуть его адрес

    static Node newNode(int val) 

    

        Node temp = new Node(); 

        temp.val = val; 

        temp.left = null;

        temp.right = null

        return temp; 

    

  

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

    static int maxPathLenUtil(Node root, 

                int prev_val, int prev_len) 

    

        if (root == null

            return prev_len; 

  

        // Получить значение Current Node

        // Значение текущего узла будет

        // предыдущий узел для его левого и правого детей

        int cur_val = root.val; 

  

        // Если текущий узел должен быть частью

        // последовательный путь, тогда он должен быть на 1 больше

        // чем значение предыдущего узла

        if (cur_val == prev_val+1) 

        

  

            // а) Найти длину левого пути

            // б) Найти длину правильного пути

            // Возвращаем максимум левого пути и правого пути

            return Math.Max(maxPathLenUtil(root.left, cur_val, prev_len+1), 

                    maxPathLenUtil(root.right, cur_val, prev_len+1)); 

        

  

        // Находим длину максимального пути под поддеревом с этим

        // узел (путь может включать или не включать этот узел)

        int newPathLen = Math.Max(maxPathLenUtil(root.left, cur_val, 1), 

                            maxPathLenUtil(root.right, cur_val, 1)); 

  

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

        // с этим узлом.

        return Math.Max(prev_len, newPathLen); 

    

  

    // Оболочка над maxPathLenUtil ().

    static int maxConsecutivePathLength(Node root) 

    

        // Возвращаем 0, если root равен NULL

        if (root == null

            return 0; 

  

        // Остальное вычисляем максимальный последовательный путь увеличения

        // Длина с использованием maxPathLenUtil.

        return maxPathLenUtil(root, root.val - 1, 0); 

    

  

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

    public static void Main(String[] args) 

    

        Node root = newNode(10); 

        root.left = newNode(11); 

        root.right = newNode(9); 

        root.left.left = newNode(13); 

        root.left.right = newNode(12); 

        root.right.left = newNode(13); 

        root.right.right = newNode(8); 

  

        Console.WriteLine("Maximum Consecutive" +

                        " Increasing Path Length is "+

                            maxConsecutivePathLength(root)); 

    

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


Выход:

Maximum Consecutive Increasing Path Length is 3

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

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

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

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

0.00 (0%) 0 votes