Учитывая двоичное дерево, где все правые узлы являются либо листовыми узлами с родственным узлом (левый узел, который имеет один и тот же родительский узел), либо пустым, переверните его вверх ногами и превратите в дерево, в котором исходные правые узлы превратились в левые листовые узлы . Верните новый рут.
Пример:
Input: [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
4
/ \
5 2
/ \
3 1
На мой взгляд, это немного сложная задача. Но все же давайте разберемся с большой проблемой и составим список дел, а затем будем надеяться, что этот вопрос будет проще.
Цель состоит в том, чтобы дерево перевернулось. Как нам добиться этого более конкретно? Обратите внимание, что если у узла есть левый дочерний элемент, его левый дочерний элемент станет новым корнем, а текущий корень - правым дочерним элементом, а текущий корень станет левым и правым дочерними элементами нового корня, соответственно. Итак, давайте составим список:
- Если у текущего корня есть левый дочерний элемент, сделайте левый дочерний элемент правой точкой на текущий корень.
- Если у текущего корня есть левый дочерний элемент, сделайте левый дочерний элемент левым, указывающим на текущий корень.
- Повторяйте описанные выше операции до тех пор, пока у текущего корня не останется левого потомка.
Но как на самом деле реализовать эту идею? Обратите внимание, что в приведенном выше примере
в самом начале мы сделаем узел 2 левой точкой 1 и правой точкой 3, но затем поддеревья узла 2 будут потеряны, поэтому очень сложно отслеживать эту информацию.
Так что давайте попробуем думать немного по-другому. Во-первых, если мы проигнорируем существование правильных поддеревьев, что мы можем получить в этом сценарии? В приведенном выше примере
1 1 / \ / 2 3 -----> 2 / \ / 4 5 4
Как выглядит это новое дерево? Это буквально эквивалентно односвязному списку, не так ли? Если узел 1 является корнем этого двоичного дерева, то он также является главой этого списка. И мы также можем рассматривать левый указатель узла как следующий указатель в узле списка. Следовательно, мы можем легко преобразовать эту проблему в проблему разворота связанного списка, и единственной дополнительной проблемой является правильное подключение для правильных поддеревьев.
Что касается соединения правых поддеревьев, давайте сделаем несколько наблюдений. Опять же, в этом примере нам нужно установить два правых соединения поддерева. Во-первых, нам нужно направить левый узел 2 на правое поддерево 1, которое является узлом 3. 2->3. Во-вторых, нам нужно указать узел 4 на узел 5, который является правым потомком 2. 4->5. Итак, единственное, что нам нужно сделать здесь, это просто указать левую точку нового корня на правый дочерний элемент на предыдущем уровне. Следовательно, мы можем просто сохранить его информацию в последнем раунде итерации и использовать ее в текущем раунде.
- Итерационное решение
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if (!root || !root->left) {
return root;
}
TreeNode* prev = NULL
TreeNode* cur = root;
TreeNode* next = NULL;
TreeNode* lastRight = NULL;
while (cur) {
next = cur->left;
cur->left = lastRight;
lastRight = cur->right;
cur->right = prev;
prev = cur;
cur = next;
}
return prev;
}
Сначала мы проверим работоспособность. Затем мы просто смоделируем алгоритм разворота односвязного списка по левой дорожке поддерева. Мы можем провести такую аналогию,
╔═══════════╦═══════════════════════╦════════════════════╗ ║ Variables ║ Binary Tree ║ Singly Linked List ║ ╠═══════════╬═══════════════════════╬════════════════════╣ ║ prev ║ parent node ║ previous node ║ ║ cur ║ current node ║ current node ║ ║ next ║ left child node ║ next node ║ ║ lastRight ║ last right child node ║ ║ ╚═══════════╩═══════════════════════╩════════════════════╝
Таким образом, мы можем резюмировать алгоритмы в несколько простых для понимания шагов:
- Сохраните следующий корень, левый дочерний элемент текущего узла.
- Подбросить. Слева указывает текущий узел на правое поддерево на последнем уровне, а справа указывает текущий узел на его родительский элемент.
- Обновите предыдущий, текущий и последний правый узел для следующей итерации. Обратите внимание, что текущий правый узел должен быть последним правым узлом в следующем раунде, но мы изменили его на шаге 2, поэтому мы можем сохранить это значение заранее или обновить его между двумя операциями переворота (как это показано в коде ).
Давайте рассмотрим приведенный выше пример:
Suppose that we are given a binary tree:
1
/ \
2 3
/ \
4 5
Initialization: prev = NULL, cur = 1, next = NULL, lastRight = NULL
1st Iteration: store 2 in next
let 1 left point to NULL (lastRight)
store 3 in lastRight
let 1 right point to NULL (prev)
move prev to 1 (cur)
move cur to 2 (next)
Binary Tree:
1
2 3
/ \
4 5
Data Structure: prev = 1, cur = 2, next = 2, lastRight = 3
2nd Iteration: store 4 in next
let 2 left point to 3 (lastRight)
store 5 in lastRight
let 2 right point to 1 (prev)
move prev to 2 (cur)
move cur to 4 (next)
Binary Tree:
1
/
2 - 3
4 5
Data Structure: prev = 2, cur = 4, next = 4, lastRight = 5
2nd Iteration: store NULL in next
let 4 left point to 5 (lastRight)
store NULL in lastRight
let 4 right point to 2 (prev)
move prev to 4 (cur)
move cur to NULL (next)
Binary Tree:
1
/
2 - 3
/
4 - 5
Data Structure: prev = 4, cur = NULL, next = NULL, lastRight = NULL
return prev = 4
Сложность времени: O (n) - n представляет длину пути от корня до его левых дочерних элементов.
Сложность пространства: O (1) - единственная основная структура данных, которую мы используем в этой реализации, - это эти четыре указателя, которые определенно представляют собой постоянную сложность пространства.
- Рекурсивное решение
Мы уже сравнивали эту проблему с простой проблемой разворота связанного списка, поэтому предполагается, что ее можно решить с помощью рекурсии. Вспомните проблему связанного списка: сначала мы рекурсивно вызываем подзадачу и пытаемся получить окончательный заголовок обратного списка результатов. А затем в текущем вызове мы делаем текущий узел последним в списке. Точно так же мы определенно можем использовать ту же стратегию. Во-первых, мы не слишком много думаем, а это означает, что мы можем напрямую вызвать подзадачу и попытаться получить возможный новый корень из этих рекурсивных вызовов. Затем мы делаем текущий корень правым дочерним элементом его левого дочернего элемента, а правый дочерний элемент текущего корня - левым дочерним элементом левого дочернего элемента корня. Формулировка немного сбивает с толку, но логика почти такая же, как и у задачи со списком.
Теперь давайте проанализируем рекурсивные правила:
- Базовый случай: когда входной корень пуст или у него нет левого дочернего элемента.
- Рекурсивное правило: 1) Получить последний новый корень из рекурсивных вызовов. 2) Сделайте текущий узел и его правый дочерний элемент дочерними по отношению к левому дочернему элементу текущего узла. Точнее, Left указывает левому дочернему элементу на правого дочернего элемента текущего корня, а right указывает левому дочернему элементу на текущий узел.
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if (!root || !root->left) {
return root;
}
TreeNode* newRoot = upsideDownBinaryTree(root->left);
root->left->left = root->right;
root->left->right = root;
root->left = NULL;
root->right = NULL;
return newRoot;
}
Мы также можем сравнить это рекурсивное решение с проблемой обращения связанного списка. Базовый случай состоит в том, что когда входной корень пуст или у него нет левого дочернего элемента, мы можем напрямую вернуть корень. Обратите внимание, что пустой случай здесь также является угловым, а не базовым, поскольку, если дерево не пусто, мы никогда не достигнем случая, когда рекурсивный вызов получает указатель NULL. Это также связано с тем, что нам нужно вернуть последний новый корень для предыдущих вызовов функций, поэтому мы должны возвращать последний узел, но не пустой. Если у текущего корня нет левого дочернего элемента, он будет в конечном итоге новым корнем после переворота, поэтому мы возвращаем его.
Для рекурсивного правила обратите внимание, что в проблеме связанного списка мы напрямую получаем окончательный результат в следующем подсписке. Здесь мы определенно можем применить ту же стратегию, чтобы сначала получить окончательный результат, а затем выполнить задачу в нашей текущей функции. Напомним, что в этой задаче со списком в каждой функции мы устанавливаем текущий узел на последний узел в списке. Теперь в двоичном дереве нам нужно установить текущий узел и его правый дочерний элемент на последний уровень в дереве. И все почти так же. Мы позволяем левому дочернему элементу указывать на текущий корень и его правый дочерний элемент, а затем устанавливаем дочерние элементы текущего корня пустыми.
Пришло время рассмотреть пример:
Suppose that we are given a binary tree:
1
/ \
2 3
/ \
4 5
Binary Tree:
1
/ \
2 3
/ \
4 5
In Main Function: call upsideDownBinaryTree(1)
Binary Tree:
1
/ \
2 3
/ \
4 5
In upsideDownBinaryTree(1): call upsideDownBinaryTree(2)
Binary Tree:
1
/ \
2 3
/ \
4 5
In upsideDownBinaryTree(2): call upsideDownBinaryTree(4)
Binary Tree:
1
/ \
2 3
/ \
4 5
In upsideDownBinaryTree(4): hit base case
return 4
Binary Tree:
1
/ \
2 3
/ \
4 5
In upsideDownBinaryTree(2): let 4 left point to 5
let 4 right point to 2
let 2 left point to NULL
let 2 right point to NULL
return 4
Binary Tree:
1
/ \
2 3
/
4 - 5
In upsideDownBinaryTree(1): let 2 left point to 3
let 2 right point to 1
let 1 left point to NULL
let 1 right point to NULL
return 4
Binary Tree:
1
/
2 - 3
/
4 - 5
In Main Function: get 4
Сложность по времени: O (n). Сложность по времени такая же, как и у итеративного решения, поскольку нам также нужно погрузиться в самый глубокий узел на самом прямом левом пути от корня.
Сложность пространства: O (n). При рекурсии нам необходимо учитывать использование стеков вызовов, поэтому в этой задаче сложность пространства также равна O (n), поскольку нам нужно n уровней стеков вызовов для самый глубокий путь рекурсии.
