Рубрики

Максимальная разница между узлом и его предком в двоичном дереве

Для данного двоичного дерева нам нужно найти максимальное значение, которое мы можем получить, вычитая значение узла B из значения узла A, где A и B — два узла двоичного дерева, а A — предок B. Ожидаемая сложность по времени равна O (п).

Например, рассмотрим ниже двоичное дерево

Мы можем иметь различную разницу между предком и узлом, некоторые из которых приведены ниже:
8 — 3 = 5
3 — 7 = -4
8 — 1 = 7
10 — 13 = -3
, , , ,

Но среди всех этих различий максимальное значение равно 7, полученному вычитанием 1 из 8, которое мы должны вернуть как результат.

Поскольку нам дано бинарное дерево, между значениями узлов нет никакой связи, поэтому нам нужно пройти через все бинарное дерево, чтобы получить максимальную разницу, и мы можем получить результат за один обход, только выполнив следующие шаги:
Если мы находимся на листовом узле, то просто возвращаем его значение, потому что он не может быть предком ни одного узла. Затем в каждом внутреннем узле мы попытаемся получить минимальное значение из левого поддерева и правого поддерева и вычислить разницу между значением узла и этим минимальным значением, и в соответствии с этим мы обновим результат.
Поскольку мы рассчитываем минимальное значение при повторной настройке, мы проверим все оптимальные возможности (проверка значения узла только с минимальным значением поддерева) различий и, следовательно, рассчитаем результат только за один обход.

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

C ++

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

using namespace std;

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

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

struct Node

{

    int key;

    struct Node* left, *right;

};

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

struct Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

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

    return (temp);

}

  
/ * Рекурсивная функция для вычисления максимального предка-узла

   Разница в двоичном дереве. Это обновляет значение в 'Res'

   сохранить результат. Возвращаемое значение этой функции

   минимальное значение в поддереве с корнем 't' * /

int maxDiffUtil(Node* t, int *res)

{

    / * Возвращаем максимальное значение int, если узел не

       там (один детский корпус) * /

    if (t == NULL)

        return INT_MAX;

  

    / * Если листовой узел, то просто вернуть значение узла * /

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

        return t->key;

  

    / * Рекурсивный вызов левого и правого поддерева

       для минимального значения * /

    int val = min(maxDiffUtil(t->left, res),

                  maxDiffUtil(t->right, res));

  

    / * Обновление res if (значение узла - минимальное значение

       из поддерева) больше, чем res * /

    *res = max(*res, t->key - val);

  

    / * Возвращаем минимальное значение, полученное до сих пор * /

    return min(val, t->key);

}

  
/ * Эта функция в основном вызывает maxDiffUtil () * /

int maxDiff(Node *root)

{

    // Инициализация результата с минимальным значением int

    int res = INT_MIN;

  

    maxDiffUtil(root, &res);

  

    return res;

}

  
/ * Вспомогательная функция для печати обхода по порядку

  бинарное дерево * /

void inorder(Node* root)

{

    if (root)

    {

        inorder(root->left);

        printf("%d ", root->key);

        inorder(root->right);

    }

}

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

int main()

{

    // Создание бинарного дерева данной диаграммы

    Node* root;

    root = newNode(8);

    root->left = newNode(3);

  

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

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

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

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

  

    root->right = newNode(10);

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

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

  

    printf("Maximum difference between a node and"

           " its ancestor is : %d\n", maxDiff(root));

}

Джава

/ * Java-программа для поиска максимальной разницы между узлами

   и его предок * /

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

class Node 

{

    int key;

    Node left, right;

   

    public Node(int key) 

    {

        this.key = key;

        left = right = null;

    }

}

   
/ * Класс Res создан для реализации передачи по ссылке

   переменной 'res' * /

class Res 

{

    int r = Integer.MIN_VALUE;

}

   

public class BinaryTree 

{

    Node root;

   

    / * Рекурсивная функция для вычисления максимального предка-узла

       Разница в двоичном дереве. Это обновляет значение в 'Res'

       сохранить результат. Возвращаемое значение этой функции

       минимальное значение в поддереве с корнем 't' * /

    int maxDiffUtil(Node t, Res res) 

    {

        / * Возвращаем максимальное значение int, если узел не

           там (один детский корпус) * /

        if (t == null)

            return Integer.MAX_VALUE;

           

        / * Если листовой узел, то просто вернуть значение узла * /

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

            return t.key;

   

        / * Рекурсивный вызов левого и правого поддерева

           для минимального значения * /

        int val = Math.min(maxDiffUtil(t.left, res),

                maxDiffUtil(t.right, res));

   

        / * Обновление res if (значение узла - минимальное значение

           из поддерева) больше, чем res * /

        res.r = Math.max(res.r, t.key - val);

   

        / * Возвращаем минимальное значение, полученное до сих пор * /

        return Math.min(val, t.key);

    }

   

    / * Эта функция в основном вызывает maxDiffUtil () * /

    int maxDiff(Node root) 

    {

        // Инициализация результата с минимальным значением int

        Res res = new Res();

        maxDiffUtil(root, res);

   

        return res.r;

    }

   

    / * Вспомогательная функция для печати обхода по порядку

       бинарное дерево * /

    void inorder(Node root) 

    {

        if (root != null

        {

            inorder(root.left);

            System.out.print(root.key + "");

            inorder(root.right);

        }

    }

   

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

   

        // Создание бинарного дерева данной диаграммы

        tree.root = new Node(8);

        tree.root.left = new Node(3);

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

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

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

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

   

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

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

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

   

        System.out.println("Maximum difference between a node and"

                + " its ancestor is : " + tree.maxDiff(tree.root));

    }

}

   
// Этот код предоставлен Mayank Jaiswal (mayank_24)

python3

# Python3 программа для поиска максимальной разницы
# между узлом и его предком

  

_MIN = -2147483648

_MAX = 2147483648

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

class newNode: 

  

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

    def __init__(self, key): 

        self.key = key

        self.left = None

        self.right = None

  
«»»
Рекурсивная функция для расчета максимума
разница между предком и узлом в двоичном дереве.
Обновляет значение в 'res', чтобы сохранить
результат. Возвращаемое значение этой функции
минимальное значение в поддереве с корнем 't' "" "

def maxDiffUtil(t, res):

  

    "" "Возвращает максимальное значение, если узел

    там нет (один детский случай) "" "

    if (t == None):

        return _MAX, res

  

    "" "Если листовой узел, то просто вернуть

        значение узла "" "

    if (t.left == None and t.right == None):

        return t.key, res

  

    "" "Рекурсивный вызов влево и вправо

    поддерево для минимального значения "" "

    a, res = maxDiffUtil(t.left, res)

    b, res = maxDiffUtil(t.right, res)

    val = min(a, b)

  

    "" "Обновление res if (значение узла - минимум

    значение из поддерева) больше, чем res "" "

    res = max(res, t.key - val)

      

    "" "Возвращение минимального значения, полученного до сих пор" ""

    return min(val, t.key), res

  
"" "Эта функция в основном вызывает maxDiffUtil ()" ""

def maxDiff(root):

  

    # Инициализация результата с минимальным значением

    res = _MIN

    x, res = maxDiffUtil(root, res)

    return res

  
"" "Вспомогательная функция для печати заказа
Обход бинарного дерева "" "

def inorder(root):

  

    if (root):

      

        inorder(root.left)

        prf("%d ", root.key)

        inorder(root.right)

      
Код водителя

if __name__ == '__main__':

      

    «»»

    Давайте создадим двоичное дерево, показанное

    в приведенном выше примере "" "

    root = newNode(8)

    root.left = newNode(3)

  

    root.left.left = newNode(1)

    root.left.right = newNode(6)

    root.left.right.left = newNode(4)

    root.left.right.right = newNode(7)

  

    root.right = newNode(10)

    root.right.right = newNode(14)

    root.right.right.left = newNode(13)

    print("Maximum difference between a node and",

          "its ancestor is :", maxDiff(root))

      
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

using System;

  
/ * C # программа для поиска максимальной разницы между узлами

   и его предок * /

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

public class Node

{

    public int key;

    public Node left, right;

  

    public Node(int key)

    {

        this.key = key;

        left = right = null;

    }

}

  
/ * Класс Res создан для реализации передачи по ссылке

   переменной 'res' * /

public class Res

{

    public int r = int.MinValue;

}

  

public class BinaryTree

{

    public Node root;

  

    / * Рекурсивная функция для вычисления максимального предка-узла

       Разница в двоичном дереве. Это обновляет значение в 'Res'

       сохранить результат. Возвращаемое значение этой функции

       минимальное значение в поддереве с корнем 't' * /

    public virtual int maxDiffUtil(Node t, Res res)

    {

        / * Возвращаем максимальное значение int, если узел не

           там (один детский корпус) * /

        if (t == null)

        {

            return int.MaxValue;

        }

  

        / * Если листовой узел, то просто вернуть значение узла * /

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

        {

            return t.key;

        }

  

        / * Рекурсивный вызов левого и правого поддерева

           для минимального значения * /

        int val = Math.Min(maxDiffUtil(t.left, res), maxDiffUtil(t.right, res));

  

        / * Обновление res if (значение узла - минимальное значение

           из поддерева) больше, чем res * /

        res.r = Math.Max(res.r, t.key - val);

  

        / * Возвращаем минимальное значение, полученное до сих пор * /

        return Math.Min(val, t.key);

    }

  

    / * Эта функция в основном вызывает maxDiffUtil () * /

    public virtual int maxDiff(Node root)

    {

        // Инициализация результата с минимальным значением int

        Res res = new Res();

        maxDiffUtil(root, res);

  

        return res.r;

    }

  

    / * Вспомогательная функция для печати обхода по порядку

       бинарное дерево * /

    public virtual void inorder(Node root)

    {

        if (root != null)

        {

            inorder(root.left);

            Console.Write(root.key + "");

            inorder(root.right);

        }

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        // Создание бинарного дерева данной диаграммы

        tree.root = new Node(8);

        tree.root.left = new Node(3);

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

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

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

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

  

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

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

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

  

        Console.WriteLine("Maximum difference between a node and" + " its ancestor is : " + tree.maxDiff(tree.root));

    }

}

  

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

Выход :

Maximum difference between a node and its ancestor is : 7 

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

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

Максимальная разница между узлом и его предком в двоичном дереве

0.00 (0%) 0 votes