Help needed with a hard facebook interview problem

Revision en2, by 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

Tags #interview, #facebook, #tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Romok007 2020-06-24 12:50:20 8
en1 English Romok007 2020-06-24 12:49:26 1125 Initial revision (published)