Удалите все узлы в двоичной тройке, которые не лежат ни на одном пути с суммой>= k

Question

Не в состоянии понять ответ дан ЗДЕСЬ Может кто-нибудь, пожалуйста, помогите понять.

Мой Алго:

Рекурсивно найти сумму каждого пути. Если сумма>=k, поместите все узлы в пути в хэш-набор. В конце переберите дерево, удалите узлы, которых нет в хэш-наборе.

Я уверен, что здесь есть много возможностей для улучшения.

Answer 1

У вас есть дерево, и вы рекурсивно анализируете его так:

go_node(Node node){
  go_node(node.left);
  go_node(node.right);
}

В вашем примере вы хотите удалить любое поддерево, значение которого меньше заданного числа. Решение простое, мы немного изменим нашу простую функцию и проблема будет решена. Я позволил "K" быть глобальной переменной, чтобы сделать этот код максимально простым. Однако вы можете проанализировать его и в методе go_node.

int go_node(Node node, int value){
  this.total_value = value;
  total_value += go_node(node.left, value);
  if (node.left.total_value < K){
     node.left = null;
  }
  total_value += go_node(node.right, value);
  if (node.right.total_value < K){
     node.right = null;
  }
  return total_value;
}

Почему я теперь могу их удалить? Когда какое-либо значение возвращается из левого или правого поддерева, это поддерево "закончено", оно обрабатывается и, что важно, - это дает мне добавление всего этого поддерева. Поэтому, когда total_value этого узла меньше K, это означает, что ЭТОТ узел и ВСЕ дочерние элементы этого узла (и дочерние элементы дочерних элементов и т. Д.) Меньше K. Причина, когда дочерний элемент поддерева возвращает мне значение, которое имеет этот дочерний элемент в total_value. сохранено значение всего поддерева.

Answer 2

Подход состоит в том, чтобы пройти по дереву и удалить узлы снизу вверх. Обходя дерево, рекурсивно рассчитайте сумму узлов от корневого до конечного узла каждого пути. Для каждого посещенного узла проверяется общая рассчитанная сумма по отношению к заданной сумме "k". Если сумма меньше, чем k, то освободите (удалите) этот узел (конечный узел) и верните сумму обратно на предыдущий узел.

public int removeNodesUtil(Node node, int sum, int k)
{
    if (node == null) return sum;

    sum =sum + node.data;
    if (node.left == null && node.right == null) 
    {
        if (sum < k)
        {
            node = null;
        }
        return sum;
    }
    int leftSum = 0, rightSum = 0, maxSum = 0;

    if (node.left != null) {
        leftSum = removeNodesUtil(node.left, sum, k);
        if (leftSum < k) {
            node.left = null;
        }
    }

    if (node.right != null) {
        rightSum = removeNodesUtil(node.right, sum, k);
        if (rightSum < k) {
            node.right = null;
        }
    }
    maxSum = Math.max(leftSum, rightSum);
    if (maxSum < k) {
        node = null;
    }
    return maxSum;
}