Блог пользователя Romok007

Help needed with a hard facebook interview problem
Автор Romok007, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Bound on the size of the tree?

→ Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится -15 Проголосовать: не нравится 
#include <algorithm>
struct Node {
  double val;
  Node* l;
  Node* r;
};
const double EPS = 1e-9;
bool isSame(double a, double b) { return std::abs(a - b) < EPS; }
double recurse(Node* v, int& count) {
  double avg;
  if (v->l == nullptr && v->r == nullptr) {
    return v->val;
  } else if (v->l == nullptr && v->r != nullptr) {
    avg = recurse(v->r, count);
  } else if (v->l != nullptr && v->r == nullptr) {
    avg = recurse(v->l, count);
  } else {
    avg = (recurse(v->l, count) + recurse(v->r, count)) / 2;
  }
  if (!isSame(v->val, avg)) {
    count++;
  }
  return avg;
}
int answer(Node* v) {
  int count;
  recurse(v, count);  // stack overflow
  return count;
}
→ Ответить