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

У меня возникла проблема во время одного из моих фиктивных интервью, где я должен был выяснить, как долго бинарное дерево полностью сгорит после того, как один данный узел уже горит.

"Бинарное дерево начинает гореть с листового узла. время (1 секунда на запись от узла к узлу), необходимое для получения всего дерева сожжен? Огонь распространится на все пути от узла. "

Скажем, у вас есть такое дерево, где N - это узел, который горит. Это происходит в первую секунду, где секунды s, поэтому в нулях s:

           1
       /       \
      1          1
    /  \          \
   1    1          1
      /   \         \
     1     N         1
                      \
                       1

После того, как пройдет одна секунда, дерево будет обновлено с использованием более сожженных узлов. Пример следующей секунды (s + 1) будет таким:

           1
       /       \
      1          1
    /  \          \
   1    N          1
      /   \         \
     1     N         1
                      \
                       1

Пример следующей секунды (s + 2) будет выглядеть так:

           1
       /       \
      N          1
    /  \          \
   1    N          1
      /   \         \
     N     N         1
                      \
                       1

Теперь на третьей секунде (s + 3) будет так:

           N
       /       \
      N          1
    /  \          \
   N    N          1
      /   \         \
     N     N         1
                      \
                       1

При том же шаблоне дерево будет записано в (s + 7)

           N
       /       \
      N          N
    /  \          \
   N    N          N
      /   \         \
     N     N         N
                      \
                       N

Поняв немного, я провел небольшое исследование, чтобы выяснить, как это сделать. Я нашел эту классную статью article и продолжил ее и реализовал идею, лежащую в основе.

Мой подход состоял в том, чтобы найти диаметр и высоту дерева, чтобы найти самый дальний узел к узлу. Однако, когда я реализовал свои функции, я только получаю результат начального узла starting node до конца данного узла given node без проверки предыдущих родительских узлов. Вот моя реализация в Python 3:

# Tree class
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

# Maximum height of a tree
def maxHeight(root):
    if root is None:
        return 0
    else:
        return 1 + max(maxHeight(root.left), maxHeight(root.right))

# Diameter of the tree
def maxDiameter(root):
    how_long = 0
    if root is None:
        return 0
    else:
        root_diameter = maxHeight(root.left) + maxHeight(root.right)

        left_diameter = maxDiameter(root.left)
        right_diameter = maxDiameter(root.right)
        how_long = max(max(left_diameter, right_diameter), root_diameter)
        return how_long

# Sample code
root = Node(1)
root.left = Node(1)
root.right = Node(1)
root.left.left = Node(1)
root.left.right = Node(1)
root.left.right.left = Node(1)
root.left.right.right = Node(1)
root.right.right = Node(1)
root.right.right.right = Node(1)
root.right.right.right.right = Node(1)
print ("Starting from the given node, it will take %ds to burn the whole tree" % (maxDiameter(root.left.right)))

Ожидаемый вывод для этого примера должен быть 6 с (начиная с 0 с данного узла). Но опять же, я не получаю полный объем дерева. Насколько я понимаю, это должно работать со всеми делами. Итак, какой поиск будет полезен здесь, DFS или BFS? Думаю, это поможет мне найти решение, но опять же. Любые отзывы приветствуются :)

Ответы

Ответ 1

Для тех, кто интересуется, что случилось с этим сообщением, было использовано следующее решение:

LeafSide = []

class Node:
    """Tree class."""

    def __init__(self, key):
        """Declare values of a node."""
        self.left = None
        self.right = None
        self.value = key


def leafHeight(root, leaf):
    """Height of the leaf."""
    if root is None:
        return 0
    else:
        if root.left is leaf:
            aux = 1 + leafHeight(root.right, leaf)
            LeafSide.append(aux)
            return 1
        if root.right is leaf:
            aux = 1 + leafHeight(root.left, leaf)
            LeafSide.append(aux)
            return 1
        return 1 + max(leafHeight(root.left, leaf), leafHeight(root.right, leaf))


def timeBurn(root, leaf):
    """How long will it take to burn the the node to furthest node."""
    hl = leafHeight(root.left, leaf)
    hr = leafHeight(root.right, leaf)
    opposite_LeafSide = 1 + hl + hr
    return max(opposite_LeafSide, LeafSide[0])


if __name__ == '__main__':
    root = Node(1)
    root.left = Node(1)
    root.right = Node(1)
    root.left.left = Node(1)
    root.left.right = Node(1)
    root.left.right.left = Node(1)
    root.left.right.right = Node(1)
    root.right.right = Node(1)
    root.right.right.right = Node(1)
    root.right.right.right.right = Node(1)
    print ("Starting from the given node, it will take %ds to burn the whole tree" % (timeBurn(root, root.left.right)))

Время: O (n)

Пробел: O (n)

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

Ответ 2

Мне приходит в голову, что вам нужно следующее:

  1. Будет ли исходный узел левым или правым корнем.
  2. Глубина стартового узла (назовите его dStart).
  3. Глубина узла, наиболее удаленного от корня на ветке начального узла (т.е. слева или справа от корня). Мы будем называть это dSameSide
  4. Глубина самого низкого общего предка стартового узла и узла, указанного в № 3. (назовите его dCommonAncestor)
  5. Глубина нижнего узла на противоположной стороне дерева, dOppositeSide.

Вы можете получить всю эту информацию из одного обходного пути дерева.

Количество шагов, которые требуется для перехода от стартового узла к самому глубокому узлу на этой стороне дерева (dSameSide - dCommonAncestor) + (dStart - dCommonAncestor).

Количество шагов, которое требуется для перехода от стартового узла к самому глубокому узлу на противоположной стороне, это (dStart + dOppositeSide).

И количество шагов, которые требуется для сжигания всего дерева, - это максимум этих двух.

Я оставлю эту реализацию вам. Вы, вероятно, найдете, как найти самый низкий общий предк двух узлов в любом двоичном дереве? полезно.

Ответ 3

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

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

Это похоже на решение, описанное в m69.

Это выполняется в O (n) времени, так как функция работает в постоянное время (если вы исключаете рекурсивные вызовы), и функция вызывается не более трех раз для каждого узла (для самого узла и для его левого и правого детей, в случай листовых узлов).

Это будет использовать пространство O (высота), поскольку мы не храним ничего кроме вызовов функций с их переменными, а максимальное количество тех, которые мы можем иметь в памяти в любой момент времени, равно глубине рекурсии (то есть высота дерева).

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

# returns a tuple (max = the longest path so far, dist = current path)
def _recurse(node, start):
    if node is None:
        return (None, 0)
    else:
        max_left, dist_left = _recurse(node.left, start)
        max_right, dist_right = _recurse(node.right, start)
        # this node is the starting node
        if node == start:
            return (0, 0)
        # the starting node is in left or right
        elif max_right is not None or max_left is not None:
            return (dist_right + dist_left + 1,
                    (dist_left if max_right is None else dist_right) + 1)
        # we haven't seen the starting node
        else:
            return (None, max(dist_left, dist_right) + 1)

def time_to_burn(root, start):
    return _recurse(root, start)[0]

Тестовое задание:

root = Node(1)
root.left = Node(1)
root.right = Node(1)
root.left.left = Node(1)
root.left.right = Node(1)
root.left.right.left = Node(1)
root.left.right.right = Node(1)
root.right.right = Node(1)
root.right.right.right = Node(1)
root.right.right.right.right = Node(1)

>>> time_to_burn(root, root.left.right.right)
7

Решение, которое работает с нелистовыми исходными узлами

Основная идея состоит в том, чтобы иметь 3 возвращаемых значения для каждого узла:

  • max, который является самым длинным путем от начального узла, полученного до сих пор (или None если мы еще не видели начальный узел).
  • above, это число узлов над стартовым узлом (или None если мы еще не видели начальный узел).
  • below, это самый длинный путь ниже стартового узла (или только самый длинный путь от текущего узла, если мы еще не видели начальный узел).

Вычисление above и below из дочерних поддеревьев довольно прямолинейно - см. Код для подробностей.

Мы можем определить самый длинный путь max от текущего узла как максимум:

  • Самый длинный путь, идущий вниз от стартового узла (который находится чуть below)
  • и самый длинный путь, который включает в себя текущий узел, который будет расстоянием от текущего узла до стартового узла плюс самый длинный путь в поддереве без стартового узла (плюс один).

Код: (заменив функцию _recurse выше)

# returns a tuple (max, above, below)
def _recurse(node, start):
    if node is None:
        return (None, None, 0)
    else:
        max_left, above_left, below_left = _recurse(node.left, start)
        max_right, above_right, below_right = _recurse(node.right, start)
        # this node is the starting node
        if node == start:
            below = max(below_left, below_right)
            return (below, 0, below)
        # the starting node is in left or right
        elif above_right is not None or above_left is not None:
            return (max((0 if above_right is None else above_right) + below_left,
                        (0 if above_left is None else above_left) + below_right) + 1,
                    (above_right if above_left is None else above_left) + 1,
                    below_right if above_left is None else below_left)
        # we haven't seen the starting node
        else:
            return (None, None, max(below_left, below_right) + 1)

>>> time_to_burn(root, root.left.right)
6

Ответ 4

Возьмите пример ниже; сначала, переходя от корня к листу в огне (F):

     N
    / \
   N   N
  / \   \
 N   N   N
    / \   \
   N   F   N
  / \       \
 N   N       N
      \
       N

Затем перейдите к его родительскому узлу и возьмите сумму расстояния до горящего листа (1) и высоты левого поддерева (3), который равен 4:

     N
    / \
   N   N
  / \   \
 N   4   N
    / \   \
   3   1   N
  / \       \
 N   2       N
      \
       1

Итак, 4 - текущий максимум. Теперь переместитесь к родительскому узлу и возьмите сумму расстояния до горящего листа (2) и глубину левого поддерева (1), которая равна 3:

     N
    / \
   3   N
  / \   \
 1   2   N
    / \   \
   N   1   N
  / \       \
 N   N       N
      \
       N

Таким образом, текущий максимум остается 4. Теперь перейдите к родительскому узлу и возьмите сумму расстояния до горящего листа (3) и глубину правого поддерева (4), который равен 7:

     7
    / \
   3   4
  / \   \
 N   2   3
    / \   \
   N   1   2
  / \       \
 N   N       1
      \
       N

Новый максимум равен 7, и мы достигли корневого узла, поэтому 7 - это ответ, который можно проверить, посмотрев, какие узлы находятся в состоянии пожара через x секунд:

     3
    / \
   2   4
  / \   \
 3   1   5
    / \   \
   2   0   6
  / \       \
 3   3       7
      \
       4

Здесь пример, когда корень не является частью самого длинного пути:

         N            N            3                  2
        / \          / \          / \                / \
       N   N        4   N        2   1              1   3
      / \          / \          / \                / \
     N   F        3   1        N   1              2   0
    /            /            /                  /
   N            2            N                  3
  /            /            /                  /
 N            1            N                  4

Наибольшее значение было встречено 4, в родительском листе на огне.

Вот простой фрагмент кода JavaScript (я не говорю на Python, но это должно работать как псевдокод). В первом примере из моего ответа используется жестко закодированная версия дерева. Как вы увидите, он делает одно сквозное пересечение дерева.

function burn(root) {
    var maximum = 0;
    traverse(root);
    return maximum;

    function traverse(node) {
        if (node.onfire) {
            return {steps: 1, onfire: true};
        }
        var l = node.left ? traverse(node.left) : {steps: 0};
        var r = node.right ? traverse(node.right) : {steps: 0};
        if (l.onfire || r.onfire) {
            maximum = Math.max(maximum, l.steps + r.steps);
            return {steps: (l.onfire ? l.steps : r.steps) + 1, onfire: true};
        }
        return {steps: Math.max(l.steps, r.steps) + 1};
    }
}

var tree = {left: {left: {left: null, right: null}, right: {left: {left: {left: null, right: null}, right: {left: null, right: {left: null, right: null}}}, right: {left: null, right: null, onfire:true}}}, right: {left: null, right: {left: null, right: {left: null, right: {left: null, right: null}}}}}
document.write(burn(tree));

Ответ 5

Это можно сделать быстро с помощью BFS:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.parent = None
        self.value = value

    def set_left(self, other):
        self.left = other
        other.parent = self

    def set_right(self, other):
        self.right = other
        other.parent = self

def get_distance_to_furthest(node):
    visited = set()
    queue = [(node, 0)]
    max_d = 0
    while queue:
        node, d = queue.pop(0)

        if node in visited:
            continue
        visited.add(node)

        max_d = max(d, max_d)

        if node.left:
            queue.append((node.left, d + 1))
        if node.right:
            queue.append((node.right, d + 1))
        if node.parent:
            queue.append((node.parent, d + 1))

    return max_d


# Sample code
root = Node(1)
root.set_left(Node(1))
root.set_right(Node(1))
root.left.set_left(Node(1))
root.left.set_right(Node(1))
root.left.right.set_left(Node(1))
root.left.right.set_right(Node(1))
root.right.set_right(Node(1))
root.right.right.set_right(Node(1))
root.right.right.right.set_right(Node(1))
print(
    "Starting from the given node, it will take %ds to burn the whole tree"
    % (get_distance_to_furthest(root.left.right))
)

Бинарное дерево - это всего лишь особый вид графика, поэтому вы можете пройти через все узлы и отслеживать расстояние каждого узла до узла, где начинался огонь. Результатом является наибольшее расстояние, которое вы видели.

Ответ 6

Это мой подход. Основываясь на узле, у которого есть лист слева или справа, у вас есть две возможности:

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

Эти две возможности определяют два пути. Самый длинный путь - это ответ на проблему (самый длинный путь между выбранным листом и любым другим листом). Это лучше всего понять на этом рисунке на данном ожоговом (красном) узле и узле, который имеет ссылку на лист (синий)

FIGURE

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

Ответ 7

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

Подход к решению заключается в следующем:

1) Найти исходный узел в дереве и найти высоту узла (здесь мы храним его в переменной "sourceDepth")

2) Для всех предков данного исходного узла

 ->Take distance from the source node and present node 

 ->Find the height of the opposite subtree in which the source is not present

 ->Add both of the above + 1 (for the edge between ancestor and sub tree).Lets call this d

3) Возьмите максимум всех d из шага 2 и sourceDepth из шага 1, который является обязательным ответом.

Для приведенного ниже примера пусть source будет 3:

     7
    / \
   8   4
  / \   \
 10   9   3
    / \   \
   0   11   2
             \
              1

глубина источника (т.е. 3): sourceDepth = 2

Все предки источника [7, 4]

Для предков 4:

расстояние от источника равно 1, и нет поддерева в противоположном направлении от источника (то есть источник находится в правом поддереве, а левого поддерева нет). Так что вот 1.

Для предков 7

Расстояние от источника равно 2, а высота поддерева в противоположном направлении от источника равна 2. Так что здесь 2 + 2 + 1 = 5. (1 для ребра от 7 до 8)

Узел 7 правое поддерево, для которого высота = 2

   8   
  / \  
 10   9  
    / \  
   0   11

Решением в этом случае будет Макс (2,1,5), который равен 5. Так что ответ 5

Java реализация вышеупомянутого решения:

static int max = Integer.MIN_VALUE;

private static int find(TreeNode<Integer> root, int source, int sourceDepth) {

    if (root == null) {
        return -1;
    }

    if (root.getData() == source) {
        sourceDepth = getDepth(root);
        return 0;
    }

    int left = find(root.getLeft(), source, sourceDepth);
    if (left != -1) {
        int rightDepth = getDepth(root.getRight()) + 1;
        max = Math.max(rightDepth + left + 1, sourceDepth);
        return left + 1;
    }

    int right = find(root.getRight(), source, sourceDepth);
    if (right != -1) {
        int leftDepth = getDepth(root.getRight()) + 1;
        max = Math.max(leftDepth + right + 1, sourceDepth);
        return right + 1;
    }

    return -1;
}

private static int getDepth(TreeNode<Integer> root) {

    if (root == null) {
        return -1;
    }

    return Math.max(getDepth(root.getLeft()), getDepth(root.getRight())) + 1;
}

Здесь источником может быть любой покидающий узел, который даст требуемый ответ, заданный здесь.

Ответ 8

//C++ implementation
#include <bits/stdc++.h>
using namespace std;
//Constructing tree
struct Node {
    int data;
    struct Node *left,*right;
    Node(int el){
        data=el;
        left=NULL;right=NULL;
    }
};
typedef struct Node Node;
Node *root=NULL;

//Constructing tree
void getparent(Node *n,int el,Node **temp){
    if(n==NULL)return;
    if(n->data==el){
        *temp=n;
    }
    getparent(n->left,el,temp);
    getparent(n->right,el,temp);
}

//Constructing tree
void create(){
    int el;
    cin>>el;
    Node *p = new Node(el);
    if(root==NULL){
        root=p;
    }else{
        Node *temp;
        int ch;
        cin>>ch;
        getparent(root,ch,&temp);
        if(temp->left==NULL){
            temp->left=p;
        }
        else{
            temp->right=p;
        }
    }
}
//Inorder traversal of tree
void print(Node *n){
    if(n!=NULL){
        print(n->left);
        cout<<n->data<<" ";
        print(n->right);
    }
}
//Height of tree from nth node
int height(Node *n){
    if(n==NULL)return 0;
    return max( height(n->left),height(n->right) )+1;
}

//Code For calculating max time in seconds when burnt at node with value k
int diameter(Node *n,int el,int *maxx){
    if(n!=NULL ){
        if(n->data==el)return  1;
        else {
            if(diameter(n->left,el,maxx)>0){
                if(*maxx<1+diameter(n->left,el,maxx)+height(n->right) )
                                *maxx=1+diameter(n->left,el,maxx)+height(n->right);
                return 1+diameter(n->left,el,maxx);
            }else if(diameter(n->right,el,maxx)>0) {
                if(*maxx<1+diameter(n->right,el,maxx)+height(n->left) )
                                *maxx=1+diameter(n->right,el,maxx)+height(n->left);
                return 1+diameter(n->right,el,maxx);
            }
            return 0;
        }
    }
    return 0;
}

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        create();
    }
    print(root);
    cout<<"\n";
    int k;
    cin>>k;
    int maxx=0;
    diameter(root,k,&maxx);
    cout<<"Time taken will be : "<<maxx<<"\n";
}


//It is working fine . I made the tree to make it understandable.

Ответ 9

Это не в моей голове, но в среднем ответ - ln(n) потому что это тот же самый алгоритм, что и поиск по сортированному двоичному дереву.

edit: Я был неправ. Я думал в своей голове "самый быстрый путь от X до Y", который является ln (n), однако это на самом деле "самый длинный путь от X до всего". Это не бинарный поиск.