Задача: 1469. Find All The Lonely Nodes
Сложность: easy

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

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

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

👨‍💻 Алгоритм:

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣ Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def DFS(self, root, isLonely, ans):
        if root is None:
            return
        
        if isLonely:
            ans.append(root.val)
        
        self.DFS(root.left, root.right is None, ans)
        self.DFS(root.right, root.left is None, ans)
    
    def getLonelyNodes(self, root):
        ans = []
        self.DFS(root, False, ans)
        return ans

Ставь 👍 и забирай 📚 Базу знаний