Найдите сумму всех левых листовых узлов, у которых также есть правый брат.

Опубликовано: 20 Сентября, 2022

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

Примеры :

Input:          16
                 /      
            20         15
           /         /    
     100      21       25
     /        /          /  
27       14    9    7    6
          /      
     17   12    2
Output: 24.
Explanation: The leaf nodes having values 7 and 17 only have a right sibling.

Input:              12
                      /    
                  13     10
                          /  
                      14    15
                             /  
                          22   23 

Output: 49

Подход: Идея состоит в том, чтобы использовать рекурсию для решения этой проблемы. Начните обход с корневого узла. Для каждого узла проверьте, является ли он NULL , если это правда, верните 0. Если оба дочерних элемента равны NULL , верните 0 . Если оба потомка не NULL :

  • Если левый является конечным узлом, тогда верните root->left->data + значение, полученное при обходе правого дочернего элемента.
  • Иначе возвращаемое значение при обходе левого дочернего элемента + значение при обходе правого дочернего элемента

Выполните следующие шаги, чтобы решить проблему:

  • Если root равен null или конечный узел, то вернуть 0.
  • Если у root есть оба дочерних элемента, выполните следующие задачи:
    • Если левый дочерний элемент root является конечным узлом, тогда верните root->left->data + sumOfLeft(root->right).
    • В противном случае вернуть сумму sumofLeft(root->left) и sumofLeft(root->right).
  • В противном случае, если есть root->left, то вернуть sumofLeft(root->left).
  • В противном случае верните sumofLeft (root-> right).

Ниже приведена реализация вышеуказанного подхода


Временная сложность: O(N), где N — общее количество узлов.
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ