Минимальное время, чтобы сжечь дерево, начиная с узла листа

Опубликовано: 6 Января, 2022

Дано двоичное дерево и листовой узел этого дерева. Известно, что за 1 секунду все узлы, подключенные к данному узлу (левый дочерний, правый дочерний и родительский), сгорают за 1 секунду. Тогда все узлы, которые связаны через один промежуточный узел, сгорают за 2 секунды, и так далее. Задача - найти минимальное время, необходимое для записи полного двоичного дерева.

Примеры:

Вход : 
            1
       / 
      2 3
    /  
   4 5 6
      /  
     7 8 9
                      
                       10
Лист = 8
Выход: 7
Первоначально 8 настроен на срабатывание на 0-й секунде.
            1
       / 
      2 3
    /  
   4 5 6
      /  
     7 П 9
                      
                       10
Через 1с : 5 поджигается.
            1
       / 
      2 3
    /  
   4 ж 6
      /  
     7 П 9
                      
                       10
После 2сек : 2, 7 поджигаются.
            1
       / 
      П 3
    /  
   4 ж 6
      /  
     FF 9
                      
                       10
После 3s : 4, 1 поджигается.
            F
       / 
      П 3
    /  
   FF 6
      /  
     FF 9
                      
                       10
Через 4 с : 3 срабатывает.
            F
       / 
      FF
    /  
   FF 6
      /  
     FF 9
                      
                       10
Через 5 с : зажигается 6.
            F
       / 
      FF
    /  
   FFF
      /  
     FF 9
                      
                       10
Через 6 с : 9 зажигается.
            F
       / 
      FF
    /  
   FFF
      /  
     FFF
                      
                       10
Через 7с : 10 поджигается.
            F
       / 
      FF
    /  
   FFF
      /  
     FFF
                      
                       F
Чтобы сжечь все дерево, требуется 7 секунд.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Идея состоит в том, чтобы хранить дополнительную информацию для каждого узла:

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

Прежде чем продолжить этот подход, давайте взглянем на дерево ниже:

В приведенном выше дереве, если мы подожжем листовой узел 11.

In 1s, the fire will reach node 9.
In 2s, the fire will reach node 5.
In 3rd second, the fire will reach node 2 and 10. Here comes an observation:
- In 2s fire reached node 5. For node 5, the initial burned leaf is in it’s left subtree, so the time taken to burn right subtree will be the height of the right subtree which is 1. Therefore, fire reaches to node 10 in (2+1) = 3s.
- Again, for the node 2. Fire reached to node 2 in 3s from right subtree. Therefore, time taken to burn left subtree will be it’s height.

So the solution is to apply recursion and for every node calculate the below-required values:

Left Depth.
Right Depth.
The time required for fire to reach the current node.
Is the current subtree conatins initial burnt leaf node.

So, for the minimum time required to burn any subtree will be:

The time required for fire to reach the root node from initial burnt leaf + depth of the opposite side

Therefore, to find time required to burn the complete tree, we need to calculate the above value for every node, and take maximum of that value.

ans = max(ans, (time required for fire to reach current node + depth of other subtree))

Below is the implementation of the above approach:

C++

// C++ program to find minimum time required
// to burn the binary tree completely
  
#include <bits/stdc++.h>
using namespace std;
  
// Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;
  
    Node()
    {
        left = NULL;
        right = NULL;
    }
};
  
// Utility function to create a new Node
Node* newNode(int val)
{
    Node* temp = new Node;
  
    temp->data = val;
  
    return temp;
}
  
/*  
    ***********ADDITIONAL INFO*************
    lDepth - maximum height of left subtree
    rDepth - maximum height of right subtree
    contains - stores true if tree rooted at current node 
               contains the first burnt node
    time - time to reach fire from the initally burnt leaf 
           node to this node
*/
struct Info {
    int lDepth;
    int rDepth;
    bool contains;
  
    int time;
  
    Info()
    {
        lDepth = rDepth = 0;
        contains = false;
  
        time = -1;
    }
};
  
/*  
    Function to calculate time required to burn 
    tree completely
      
    node - address of current node
    info - extra information about current node
    target - node that is fired
    res - stores the result
*/
Info calcTime(Node* node, Info& info, int target, int& res)
{
  
    // Base case: if root is null
    if (node == NULL) {
        return info;
    }
  
    // If current node is leaf
    if (node->left == NULL && node->right == NULL) {
  
        // If current node is the first burnt node
        if (node->data == target) {
            info.contains = true;
            info.time = 0;
        }
        return info;
    }
  
    // Information about left child of root
    Info leftInfo;
    calcTime(node->left, leftInfo, target, res);
  
    // Information about right child of root
    Info rightInfo;
    calcTime(node->right, rightInfo, target, res);
  
    // If left subtree contains the fired node then
    // time required to reach fire to current node
    // will be (1 + time required for left child)
    info.time = (node->left && leftInfo.contains) ? (leftInfo.time + 1) : -1;
  
    // If right subtree contains the fired node then
    // time required to reach fire to current node
    // will be (1 + time required for right child)
    if (info.time == -1)
        info.time = (node->right && rightInfo.contains) ? (rightInfo.time + 1) : -1;
  
    // Storing(true or false) if the tree rooted at
    // current node contains the fired node
    info.contains = ((node->left && leftInfo.contains) || (node->right && rightInfo.contains));
  
    // Calculate the maximum depth of left subtree
    info.lDepth = !(node->left) ? 0 : (1 + max(leftInfo.lDepth, leftInfo.rDepth));
  
    // Calculate the maximum depth of right subtree
    info.rDepth = !(node->right) ? 0 : (1 + max(rightInfo.lDepth, rightInfo.rDepth));
  
    // Calculating answer
    if (info.contains) {
        // If left subtree exists and
        // it contains the fired node
        if (node->left && leftInfo.contains) {
            // calculate result
            res = max(res, info.time + info.rDepth);
        }
  
        // If right subtree exists and it
        // contains the fired node
        if (node->right && rightInfo.contains) {
            // calculate result
            res = max(res, info.time + info.lDepth);
        }
    }
}
  
// Driver function to calculate minimum
// time required
int minTime(Node* root, int target)
{
    int res = 0;
    Info info;
  
    calcTime(root, info, target, res);
  
    return res;
}
  
// Driver Code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->left->left->left = newNode(8);
    root->left->right->left = newNode(9);
    root->left->right->right = newNode(10);
    root->left->right->left->left = newNode(11);
  
    // target node is 8
    int target = 11;
  
    cout << minTime(root, target);
  
    return 0;
}

Java

// Java program to find minimum time required
// to burn the binary tree completely
  
public class GFG {
  
    // Tree Node
    static class Node {
        int data;
        Node left, right;
  
        Node(int data)
        {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
  
    /* 
        ***********ADDITIONAL INFO*************
        lDepth - maximum height of left subtree
        rDepth - maximum height of right subtree
        contains - stores true if tree rooted at current node 
                contains the first burnt node
        time - time to reach fire from the initally burnt leaf 
            node to this node
    */
    static class Data {
        int leftDepth, rightDepth, time;
        boolean contains;
  
        Data()
        {
            contains = false;
            leftDepth = rightDepth = 0;
            time = -1;
        }
    }
  
    /* 
        Function to calculate time required to burn 
        tree completely
          
        node - address of current node
        info - extra information about current node
        target - node that is fired
        res - stores the result
    */
    public static void getResult(Node node, Data data, int target)
    {
  
        // Base case: if root is null
        if (node == null) {
            return;
        }
  
        // If current node is leaf
        if (node.left == null && node.right == null) {
  
            // If current node is the first burnt node
            if (node.data == target) {
                data.contains = true;
                data.time = 0;
            }
            return;
        }
  
        // Information about left child
        Data leftData = new Data();
        getResult(node.left, leftData, target);
  
        // Information about right child
        Data rightData = new Data();
        getResult(node.right, rightData, target);
  
        // If left subtree contains the fired node then
        // time required to reach fire to current node
        // will be (1 + time required for left child)
        data.time = (leftData.contains) ? (leftData.time + 1) : -1;
  
        // If right subtree contains the fired node then
        // time required to reach fire to current node
        // will be (1 + time required for right child)
        if (data.time == -1)
            data.time = (rightData.contains) ? (rightData.time + 1) : -1;
  
        // Storing(true or false) if the tree rooted at
        // current node contains the fired node
        data.contains = (leftData.contains || rightData.contains);
  
        // Calculate the maximum depth of left subtree
        data.leftDepth = (node.left == null) ? 0 : (1 + Math.max(leftData.leftDepth, leftData.rightDepth));
  
        // Calculate the maximum depth of right subtree
        data.rightDepth = (node.right == null) ? 0 : (1 + Math.max(rightData.leftDepth, rightData.rightDepth));
  
        // Calculating answer
        if (data.contains) {
  
            // If left subtree exists and
            // it contains the fired node
            if (leftData.contains) {
  
                // calculate result
                res = Math.max(res, data.time + data.rightDepth);
            }
  
            // If right subtree exists and it
            // contains the fired node
            if (rightData.contains) {
  
                // calculate result
                res = Math.max(res, data.time + data.leftDepth);
            }
        }
    }
  
    // To store the result
    public static int res;
  
    // Driver Code
    public static void main(String args[])
    {
  
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.left.left.left = new Node(8);
        root.left.right.left = new Node(9);
        root.left.right.right = new Node(10);
        root.left.right.left.left = new Node(11);
  
        int target = 11;
  
        res = 0;
        getResult(root, new Data(), target);
        System.out.println(res);
    }
}

C#

// C# program to find minimum time required
// to burn the binary tree completely
using System;
  
class GFG 
{
  
    // Tree Node
    class Node 
    {
        public int data;
        public Node left, right;
  
        public Node(int data)
        {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
  
    /* 
        ***********ADDITIONAL INFO*************
        lDepth - maximum height of left subtree
        rDepth - maximum height of right subtree
        contains - stores true if tree rooted at current node 
                contains the first burnt node
        time - time to reach fire from the initally burnt leaf 
            node to this node
    */
    class Data 
    {
        public int leftDepth, rightDepth, time;
        public bool contains;
  
        public Data()
        {
            contains = false;
            leftDepth = rightDepth = 0;
            time = -1;
        }
    }
  
    

Курсы Skillbox

Минимальное время, чтобы сжечь дерево, начиная с узла листа

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ