Распределить монеты в двоичном дереве
Я ищу решения проблемы LeetCode 979. Распределение монет в двоичном дереве:
Вам дана
rootбинарного дерева сnузлами, где каждыйnodeв дереве имеетnode.valмонеты. Всего по всему деревуnмонет.За один ход мы можем выбрать два соседних узла и переместить одну монету из одного узла в другой. Перемещение может осуществляться от родителя к дочернему элементу или от дочернего элемента к родительскому.
Возвращает минимальное количество ходов, необходимое для того, чтобы в каждом узле была ровно одна монета.
Я анализирую решение вотрубака на C++
int traverse(TreeNode* r, int &moves) {
if (r == nullptr) return 0;
int left = traverse(r->left, moves), right = traverse(r->right, moves);
moves += abs(left) + abs(right); // <----- do not understand
return r->val + left + right - 1;
}
int distributeCoins(TreeNode* r, int moves = 0) {
traverse(r, moves);
return moves;
}
Мне трудно это понять:
- почему
move = move + abs(left) + abs(right)в текущем поддереве? - почему мы не привлекаем
curr_node? напримерmove = move + abs(curr_node) + abs(left) + abs(right)? - означает ли это, что в каждом поддереве ход
abs(left) + abs(right)равен ходам только левого поддерева и только правого поддерева? - в верхнем корневом поддереве у нас есть
move = abs(left) + abs(right), значит, для корневого узла нет перемещения? Похожеabs(left)ИЛИabs(right)прикрыть перемещение корневого узла?
@user24714692 user24714692, моя проблема не в move = move + xxxx. Моя проблема в том, что для каждого поддерева мы говорим sub move = abs(left) + abs(right) без участия текущего узла. в конечном корне общее движение = суб пресс (слева) + суб пресс (справа). вы можете видеть, что abs(left) или abs(right) охватывают операцию корневого узла, например. корень 0 -> левый 3 -> правый 0. Это 3 оп; перемещение = левый абс (2) + правый абс (1); вы можете видеть, что левая крышка закрывает операцию корневого узла. В основном в финальной корневой операции левое и правое автоматическое закрытие корневого узла. вопрос в том, почему нам не нужно учитывать текущий узел подсчета ходов на протяжении всего пути
Это простой вопрос. Почему бы вам не задействовать текущий узел и не посмотреть, что произойдет? Обратите внимание, что цель состоит в том, чтобы подсчитать только ходы, необходимые для распределения монет между узлами, чтобы гарантировать, что в каждом узле останется ровно одна монета. Также обратите внимание, что это распространенный метод «не задействовать текущий узел». Аналогичным образом он используется в максимальной сумме пути и в некоторых других задачах.
@trincot извини, забыл
Ответы 1
Давайте сначала опишем значение задействованных переменных:
Значение переменных
Переменная left представляет количество монет, которых слишком много в левом поддереве, т. е. которые необходимо переместить из этого поддерева через ребро между текущим узлом и его левым дочерним элементом. Если это число отрицательное, то оно представляет собой количество монет, которых не хватает в этом поддереве, т. е. которые необходимо переместить в это поддерево через это ребро.
right имеет аналогичное значение, но только для правого поддерева.
moves — это одно целое число, общее для всех контекстов выполнения, traverse, которое представляет количество необходимых ходов на данный момент. Он не делает различий между движениями «вверх» и «вниз».
Благодаря этой информации мы можем развеять ваши сомнения:
Разъяснения
почему
move = move + abs(left) + abs(right)в текущем поддереве?
Это присвоение moves учитывает количество монет, которые необходимо пройти вдоль двух конкретных ребер: ребра между текущим узлом и его левым дочерним элементом и ребра между текущим узлом и его правым дочерним элементом.
left представляет количество монет, которые необходимо пройти вверх от левого дочернего узла текущего узла к текущему узлу. Это представляет собой количество ходов, которые будут выполнены с использованием края левого дочернего узла текущего узла. Если left отрицательное значение, это значение по-прежнему представляет собой количество движений, но они просто будут происходить в противоположном направлении. Для подсчета количества ходов направление не имеет значения, поэтому берем абсолютное значение.
Следовательно, abs(left) представляет количество ходов через одно конкретное ребро — между текущим узлом и его левым дочерним элементом — и abs(right) представляет то же самое для другого дочернего ребра. Накапливая эту сумму до move, мы получаем количество ходов по всем ребрам ниже текущего узла, и поэтому, когда мы достигнем корня, мы в конечном итоге учтем ходы, которые произойдут через все ребра.
почему мы не привлекаем
curr_node? напримерmove = move + abs(curr_node) + abs(left) + abs(right)?
Поскольку мы знаем, что в дереве столько же монет, сколько и узлов, у нас будет достаточно информации, если мы знаем, сколько узлов отсутствует или избыточно в поддеревьях узлов.
Возьмем пример: допустим, мы знаем, что в левом поддереве узла отсутствуют 5 монет (left — это -5), а в его правом поддереве на 2 монеты слишком много (right — 2). Теперь не имеет значения, сколько монет находится в текущем узле, чтобы решить, сколько монет должно переместиться в/из поддеревьев. Если в этом примере текущий узел оказывается корнем, то мы "не глядя" знаем, что текущий узел должен иметь 4 монеты: 1 для себя, и 2 монеты должны будут всплывать из правого поддерева, и 5 монет ( 3 у него уже было, а 2 он получил справа), которые нужно переместить в его левое поддерево.
Если текущий узел не является корнем, то если он имеет более 4 монет, то все равно у нас будут те же ходы с двумя его дочерними элементами, тогда как избытку придется позже переместиться вверх через ребро к родителю узла. Но это ребро выходит за рамки работы с текущим узлом. Алгоритм занимается этим при посещении своего родителя.
Аналогично, если текущий узел будет иметь менее 4 монет, то этот дефицит будет восполнен позже, снова, когда мы посетим его родительский узел.
Короче говоря, moves здесь увеличивается на значение, которое отражает количество ходов через два его дочерних ребра, а не количество ходов, необходимых для передачи монет через его родительское ребро. А поскольку мы знаем общее количество монет, нам не нужно знать, сколько монет содержит текущий узел, чтобы определить, сколько ходов произойдет через два его дочерних ребра.
означает ли это, что в каждом поддереве ход
abs(left) + abs(right)равен ходам только левого поддерева и только правого поддерева?
abs(left) + abs(right) представляет количество монет, которым необходимо пересечь два дочерних ребра текущего узла, и только их. Перемещение монет по более глубоким ребрам в этих поддеревьях уже было добавлено в moves.
в верхнем корневом поддереве у нас есть
move = abs(left) + abs(right), значит, для корневого узла нет перемещения? Похожеabs(left)ИЛИabs(right)прикрыть перемещение корневого узла?
Просто небольшая поправка. В коде есть +=, а не =. Когда это присвоение произойдет, move уже будет иметь накопленные значения от более глубоких ребер дерева. Они не должны потеряться, а значит += нужен.
Приведенные выше разъяснения должны ответить и на это сомнение. Если left отрицательно, то это количество монет, которые перемещаются от корневого узла к его левому дочернему узлу через это ребро к дочернему узлу. Поскольку это корневой узел, такой сценарий будет означать, что монеты доступны для этих ходов (в левое поддерево): использование лишних монет в самом корневом узле и/или лишних монет в правом поддереве корня.
Если, например, в самом корневом узле недостаточно монет, чтобы покрыть эти ходы к левому дочернему узлу, то right наверняка будет строго положительным и будет соответствовать тому, что необходимо: это число представляет собой количество монет, которые будут двигаться вверх по ребру. от правого дочернего элемента корня к корню.
Я надеюсь, что это проясняет ситуацию.
@user24714692 user24714692, если узел curr создаст 2 операции, то зачем просто перемещать = abs(left) + abs(right)?