Задача. Слияние двух бинарных деревьев
Сложность: Лёгкая
Условие задачи: Даны два бинарных дерева, необходимо осуществить их наложение друг на друга и вывод результатов в новом дереве.
Примечание: Наложение представляет из себя суммирование соответствующих значений из узлов двух деревьев.
Пример:
Ввод: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Вывод:[3,4,5,5,4,null,7]
Ввод: root1 = [1], root2 = [1,2]
Вывод: [2,2]
Решение
Напишем простую рекурсию с функцией
▪Если один из двух узлов не определен, мы можем просто вернуть другой узел.
▪Если 2 узла не определены, мы можем завершить рекурсию.
Пишите свое мнение в комментариях👇
@python_job_interview
Сложность: Лёгкая
Условие задачи: Даны два бинарных дерева, необходимо осуществить их наложение друг на друга и вывод результатов в новом дереве.
Примечание: Наложение представляет из себя суммирование соответствующих значений из узлов двух деревьев.
Пример:
Ввод: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Вывод:[3,4,5,5,4,null,7]
Ввод: root1 = [1], root2 = [1,2]
Вывод: [2,2]
Решение
Напишем простую рекурсию с функцией
constructTree.▪Если один из двух узлов не определен, мы можем просто вернуть другой узел.
▪Если 2 узла не определены, мы можем завершить рекурсию.
class Solution(object):
def mergeTrees(self, root1, root2):
def constructTree(root1, root2):
if not root1 and not root2:
return None
if not root2:
return root1
if not root1:
return root2
head = TreeNode(root1.val + root2.val)
head.left = constructTree(root1.left, root2.left)
head.right = constructTree(root1.right, root2.right)
return head
return constructTree(root1, root2)Пишите свое мнение в комментариях👇
@python_job_interview