Ежедневный вопрос по алгоритму -- leetcode 112 -- сумма путей -- python

алгоритм
Ежедневный вопрос по алгоритму -- leetcode 112 -- сумма путей -- python

【Название Описание】

【Идея кода】

На базе этой темы можете посмотреть мою следующую статью:leetcode 113 -- Сумма пути IIиleetcode 437 -- Сумма пути III

Первое, что приходит на ум при ответе на этот вопрос, — это пройти все пути от корневого узла к листовому узлу дерева, сохранить сумму каждого пути в списке и, наконец, посмотреть, содержит ли список данные, заданные название. . Чтобы пройти по всем путям дерева, вы должны сначала использовать глубину и написать рекурсивную функцию.Затем вы должны взять точку и посмотреть на нее.Возьмите узел 5, чтобы увидеть, когда входной узел рекурсивной функции равен 5.

Затем я сначала хочу оценить, есть ли у этого узла левое и правое поддеревья, и использовать переменную sum1 для хранения суммы всего пути. Моя рекурсивная функция plus(root,sum1); если есть левое поддерево, то вызовите plus(root,sum1+5); если есть правое поддерево, то вызовите plus(root,sum1+5); есть левые и правые поддеревья. Значение sum1, передаваемое при вызове рекурсивной функции, должно быть одинаковым, то есть sum1+root.val.

        if root.left:
            self.plus(root.left,sum1+root.val)
        if root.right:
            self.plus(root.right,sum1+root.val)

Если у этого узла нет ни левого, ни правого поддерева, это означает, что он является конечным узлом, затем напрямую добавьте значение конечного узла и сохраните эту сумму1 в списке.

if not root.left and not root.right:
    sum1+=root.val
    print "叶结点:",root.val,"sum1=",sum1
    self.sum_list.append(sum1)

Вызовите эту плюс рекурсивную функцию в вызывающей функции.Я определяю sum_list как атрибут класса, поэтому его можно читать и записывать непосредственно через self.sum_list внутри класса.

    self.sum_list=[]

Еще раз проверьте в вызывающей функции, включена ли сумма в sum_list.

def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """ 
        sum1=0
        if not root:return False
        self.plus(root,sum1)
        return sum in self.sum_list

【Исходный код】

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        self.sum_list=[]
        sum1=0
        if not root:return False
        self.plus(root,sum1)
        return sum in self.sum_list
    def plus(self,root,sum1):
        print "执行plus(",root.val,sum1,")"
        if not root.left and not root.right:
            sum1+=root.val
            print "叶结点:",root.val,"sum1=",sum1
            self.sum_list.append(sum1)
        if root.left:
            self.plus(root.left,sum1+root.val)
        if root.right:
            self.plus(root.right,sum1+root.val)
        return False

[Рекурсивное воспроизведение процесса]

Для лучшего понимания я беру в качестве примера дерево и распечатываю рекурсивный процесс. Дерево это:

Выполните исходный код, рекурсивный процесс:

执行plus( 5,0 )
执行plus( 4,5 )
执行plus( 11,9 )
执行plus( 7,20 )
叶结点: 7 sum1= 27
执行plus( 2,20 )
叶结点: 2 sum1= 22
执行plus( 8,5 )
执行plus( 13,13 )
叶结点: 13 sum1= 26
执行plus( 4,13 )
执行plus( 1,17 )
叶结点: 1 sum1= 18
Категории