Рубрики

Сумма всех различий между родителями и детьми в двоичном дереве

Для заданного двоичного дерева найдите сумму всех разностей между родителями и дочерними элементами для всех неконечных узлов данного двоичного дерева.
Обратите внимание, что разница родитель-потомок равна (значение родительского узла — (сумма значений дочернего узла)).

Примеры:

Input: 
        1
      /   \
     2     3
    / \   / \
   4   5 6   7
          \
           8
Output: -23
1st parent-child difference = 1 -(2 + 3) = -4
2nd parent-child difference = 2 -(4 + 5) = -7
3rd parent-child difference = 3 -(6 + 7) = -10
4th parent-child difference = 6 - 8 = -2
Total sum = -23

Input: 
        1
      /   \
     2     3
      \   /
       5 6
Output: -10

Наивный подход . Идея состоит в том, чтобы обойти дерево любым способом и проверить, является ли узел листовым или нет. Если узел является неконечным узлом, добавьте (данные узла — сумма данных дочернего узла) к результату.

Эффективный подход: в конечном результате тщательный анализ предполагает, что каждый внутренний узел (узлы, которые не являются ни корневыми, ни конечными), когда-то рассматривается как дочерний, а один — как родительский, следовательно, их вклад в конечный результат равен нулю. Кроме того, корень обрабатывается как родительский только один раз и аналогичным образом, все конечные узлы считаются дочерними. Следовательно, конечный результат равен (значение корня — сумма всех листовых узлов) .

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Структура для узла двоичного дерева

struct Node {

    int data;

    Node *left, *right;

};

  
// Возвращает новый узел

Node* newNode(int data)

{

    Node* temp = new Node();

    temp->data = data;

    temp->left = temp->right = NULL;

}

  
// Сервисная функция, которая вычисляет
// сумма всех листовых узлов

void leafSumFunc(Node* root, int* leafSum)

{

    if (!root)

        return;

  

    // Добавить корневые данные в сумму, если

    // корень - это листовой узел

    if (!root->left && !root->right)

        *leafSum += root->data;

  

    // рекурсивная проверка слева

    // и правое поддерево

    leafSumFunc(root->left, leafSum);

    leafSumFunc(root->right, leafSum);

}

  
// Функция для возврата требуемого результата

int sumParentChildDiff(Node* root)

{

  

    // Если root имеет значение null

    if (!root)

        return 0;

  

    // Если только узел является корневым узлом

    if (!root->left && !root->right)

        return root->data;

  

    // Находим сумму всех листовых узлов

    int leafSum = 0;

    leafSumFunc(root, &leafSum);

  

    // Корень - сумма всех листовых узлов

    return (root->data - leafSum);

}

  
// Код драйвера

int main()

{

    // Построить двоичное дерево

    Node* root = newNode(1);

    root->left = newNode(2);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right = newNode(3);

    root->right->right = newNode(7);

    root->right->left = newNode(6);

  

    cout << sumParentChildDiff(root);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
// Структура для узла двоичного дерева

static class Node

{

    int data;

    Node left, right;

};

  
// Возвращает новый узел

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

static int leafSum;

  
// Сервисная функция, которая вычисляет
// сумма всех листовых узлов

static void leafSumFunc(Node root )

{

    if (root == null)

        return;

  

    // Добавить корневые данные в сумму, если

    // корень - это листовой узел

    if (root.left == null && root.right == null)

        leafSum += root.data;

  

    // рекурсивная проверка слева

    // и правое поддерево

    leafSumFunc(root.left);

    leafSumFunc(root.right);

}

  
// Функция для возврата требуемого результата

static int sumParentChildDiff(Node root)

{

  

    // Если root имеет значение null

    if (root == null)

        return 0;

  

    // Если только узел является корневым узлом

    if (root.left == null && root.right == null)

        return root.data;

  

    // Находим сумму всех листовых узлов

    leafSum = 0;

    leafSumFunc(root);

  

    // Корень - сумма всех листовых узлов

    return (root.data - leafSum);

}

  
// Код драйвера

public static void main(String args[])

{

    // Построить двоичное дерево

    Node root = newNode(1);

    root.left = newNode(2);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right = newNode(3);

    root.right.right = newNode(7);

    root.right.left = newNode(6);

  

    System.out.println( sumParentChildDiff(root));

}
}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 реализация подхода

  
# Структура для узла двоичного дерева

class Node:

      

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Сервисная функция, которая вычисляет
# сумма всех листовых узлов

def leafSumFunc(root, leafSum): 

  

    if not root:

        return 0

  

    # Добавить корневые данные в сумму

    # если корень является листовым узлом

    if not root.left and not root.right: 

        leafSum += root.data

          

    # Рекурсивно проверить в

    # левое и правое поддерево

    leafSum = max(leafSumFunc(root.left, 

                              leafSum), leafSum)

    leafSum = max(leafSumFunc(root.right, 

                              leafSum), leafSum)

    return leafSum

  
# Функция для возврата требуемого результата

def sumParentChildDiff(root): 

  

    # Если root отсутствует

    if not root: 

        return 0

  

    # Если только узел является корневым узлом

    if not root.left and not root.right:

        return root.data 

  

    # Найти сумму всех листовых узлов

    leafSum = leafSumFunc(root, 0

  

    # Root - сумма всех листовых узлов

    return root.data - leafSum 

  
# Код драйвера

if __name__ == "__main__":

  

    # Построить двоичное дерево

    root = Node(1

    root.left = Node(2

    root.left.left = Node(4

    root.left.right = Node(5

    root.right = Node(3

    root.right.right = Node(7

    root.right.left = Node(6

  

    print(sumParentChildDiff(root)) 

  
# Этот код предоставлен Rituraj Jain

C #

// C # реализация подхода

using System;

      

class GFG

{

  
// Структура для узла двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

};

  
// Возвращает новый узел

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

static int leafSum;

  
// Сервисная функция, которая вычисляет
// сумма всех листовых узлов

static void leafSumFunc(Node root )

{

    if (root == null)

        return;

  

    // Добавить корневые данные в сумму, если

    // корень - это листовой узел

    if (root.left == null && root.right == null)

        leafSum += root.data;

  

    // рекурсивная проверка слева

    // и правое поддерево

    leafSumFunc(root.left);

    leafSumFunc(root.right);

}

  
// Функция для возврата требуемого результата

static int sumParentChildDiff(Node root)

{

  

    // Если root имеет значение null

    if (root == null)

        return 0;

  

    // Если только узел является корневым узлом

    if (root.left == null && root.right == null)

        return root.data;

  

    // Находим сумму всех листовых узлов

    leafSum = 0;

    leafSumFunc(root);

  

    // Корень - сумма всех листовых узлов

    return (root.data - leafSum);

}

  
// Код драйвера

public static void Main(String []args)

{

    // Построить двоичное дерево

    Node root = newNode(1);

    root.left = newNode(2);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right = newNode(3);

    root.right.right = newNode(7);

    root.right.left = newNode(6);

  

    Console.WriteLine( sumParentChildDiff(root));

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

-21

Рекомендуемые посты:

Сумма всех различий между родителями и детьми в двоичном дереве

0.00 (0%) 0 votes