LeetCode в день - сумма левых листьев

Сумма левых листьев

Ссылка на вопрос летакода

В последнее время я шлифовал лецкод и решил записать некоторые из моих мыслей в этом блоге. Это оба, чтобы помочь мне оглянуться назад на то, о чем я работал, а также помогите другим видеть, как можно подумать о проблемах.

Тем не менее, поскольку многие люди публикуют свои собственные решения в раздел дискуссий IETCODE, я не обязательно буду публиковать оптимальное решение.

Вопрос

( Копия вставлена из лецкода)

Найдите сумму всех левых листьев в данном двоичном дереве.

Пример:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

Мой подход (ES)

Я не буду преодолевать весь код для всех попыток, но я объясню свой подход (ы) качественно.

Попытка 1 – DFS

(Представлено – принято)

Когда я вижу такую проблему дерева, как это, мой Go-to DF или BFS (я обычно начинаю с DFS по умолчанию), и я склонен использовать стек (вы можете использовать рекурсию).

Принцип – просто проверять каждый узел, чтобы найти узлы, которые:

Листья
Были слева от их родителей

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

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

Я реализовал это с помощью словаря (в Python), который хранит узел и тип «NTYPE» или NODE. Тип узла в настоящее время либо «root», «вправо» или «влево». Я покинул тип в виде строки для целей быстрого представления кода, но может использоваться enum, поскольку данные могут быть только одним из возможных наборов.

Представленный код (Python):

class Solution(object):
    def sumOfLeftLeaves(self, root):

        if root == None:
            return 0
        result = 0 
        stack = [{'node': root, 'nType': 'root'}]

        # dfs using a stack 
        # add to result if left and a leaf 
        # should add an additional data, whether it was left or right or root
        while len(stack) > 0:
            curr = stack.pop() 
            currNode = curr['node']
            currType = curr['nType']

            # check if leaf 
            if currNode.left == None and currNode.right == None and currType == 'left':
                result += currNode.val

            # add children to tree 
            if currNode.left != None:
                stack.append({'node': currNode.left, 'nType': 'left'})

            if currNode.right != None:
                stack.append({'node': currNode.right, 'nType': 'right'})

        # end of while loop
        return result

Обсуждение и выводы

Как уже упоминалось в разделе «Подход», лучшая структура данных, такая как enum, может использоваться для хранения состояния текущего узла. Но моя главная забота о оптимизации производительности заключается в том, могу ли я постоянно искать меньше, чем O (n) (где n – количество узлов в дереве) узлов.

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

Оригинал: “https://dev.to/drewhsu86/leetcode-daily-sum-of-left-leaves-17k8”