Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Help needed with a hard facebook interview problem

Правка en2, от Romok007, 2020-06-24 12:50:20

Given a binary tree, return the minimum number of edits to make the value of each node equal to the average of its direct children's. Note that you can only update the value of each tree node, and changing the tree structure is not allowed.

"average of its direct children's" means the average of left and right children.

1. If the left(right) children doesn't exist, then just let the root value equal to the value of its right(left) children.

2. If the root is leaf, then the criteria is always met for this node.

3. It doesn't matter if the value is int or float. We can use float.

Sample 1 :

        2
       / \
      0   2
         / \
        0   2
           / \ 
          0   1
             / \
            0   1
               / \
              0   1

Output : 5

Sample 2 :

         2
          \
           2
            \
             2
              \
               1
                \
                 1
                  \
                   1

Output : 3

Теги #interview, #facebook, #tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Romok007 2020-06-24 12:50:20 8
en1 Английский Romok007 2020-06-24 12:49:26 1125 Initial revision (published)