Рубрики

Разница между суммами нечетного уровня и четных узлов уровня двоичного дерева

Для двоичного дерева найдите разницу между суммой узлов на нечетном уровне и суммой узлов на четном уровне. Рассмотрим root как уровень 1, левый и правый потомки root как уровень 2 и так далее.

Например, в следующем дереве сумма узлов на нечетном уровне равна (5 + 1 + 4 + 8), что равно 18. А сумма узлов на четном уровне равна (2 + 6 + 3 + 7 + 9), что составляет 27 Выход для следующего дерева должен быть 18 — 27, который равен -9.

      5
    /   \
   2     6
 /  \     \  
1    4     8
    /     / \ 
   3     7   9  

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

C реализация подхода, основанного на обходе порядка уровней, чтобы найти разницу .

Этот подход предоставлен Мандипом Сингхом. Для итеративного подхода просто проходите уровень дерева по уровням (уровень обхода порядка), сохраняйте сумму значений узлов даже в нет. уровень в evenSum и остаток в переменной oddSum и, наконец, вернуть разницу.

Ниже приведена простая реализация подхода.

C ++

// CPP программа для поиска
// разница между
// суммы нечетного уровня
// и даже узлы уровня
// двоичного дерева
#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;

    return temp;

}

  
// вернуть разницу
// суммы нечетного уровня
// и даже уровень

int evenOddLevelDifference(Node* root)

{

    if (!root)

        return 0;

  

    // создаем очередь для

    // уровень прохождения заказа

    queue<Node*> q;

    q.push(root);

  

    int level = 0;

    int evenSum = 0, oddSum = 0;

  

    // пройти до

    // очередь пуста

    while (!q.empty()) 

    {

        int size = q.size();

        level += 1;

  

        // пройти для

        // завершить уровень

        while(size > 0)

        {

            Node* temp = q.front();

            q.pop();

  

            // проверить, если уровень нет.

            // четный или нечетный и

            // соответственно обновляем

            // EvenSum или OddSum

            if(level % 2 == 0)

                evenSum += temp->data;

            else

                oddSum += temp->data;

          

            // проверка левого ребенка

            if (temp->left) 

            {

                q.push(temp->left);

            }

              

            // проверка на правильность ребенка

            if (temp->right)

            {

                q.push(temp->right);

            }

            size -= 1;

        

    }

      

    return (oddSum - evenSum);

}

  
// драйверная программа

int main()

{

    // построить дерево

    Node* root = newNode(5);

    root->left = newNode(2);

    root->right = newNode(6);

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

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

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

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

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

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

  

    int result = evenOddLevelDifference(root);

    cout << "diffence between sums is :: ";

    cout << result << endl;

    return 0;

}

  
// Эта статья предоставлена Мандипом Сингхом.

Джава

// Java-программа для поиска
// разница между
// суммы нечетного уровня
// и даже узлы уровня
// двоичного дерева

import java.io.*;

import java.util.*;

// Пользовательский класс узла

class Node {

      int data;

      Node left, right;

         

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

      Node(int key) 

      {

           data  = key;

           left = right = null;

      }

}

class GFG {

      // вернуть разницу

      // суммы нечетного уровня и четного уровня

      static int evenOddLevelDifference(Node root)

      {

             if (root == null)

                 return 0;

  

             // создаем очередь для

             // уровень прохождения заказа

             Queue<Node> q = new LinkedList<>();

             q.add(root);

  

             int level = 0

             int evenSum = 0, oddSum = 0;

  

             // пройти до

             // очередь пуста

             while (q.size() != 0) {

                   int size = q.size();

                   level++;

                     

                   // пройти полный уровень

                   while (size > 0) {

                          Node temp = q.remove();

  

                          // проверить, если уровень нет.

                          // четный или нечетный и

                          // соответственно обновляем

                          // EvenSum или OddSum

                          if (level % 2 == 0)

                              evenSum += temp.data;

                          else

                              oddSum += temp.data;

  

                          // проверка левого ребенка

                          if (temp.left != null)

                              q.add(temp.left);

                             

                          // проверка на правильность ребенка

                          if (temp.right != null)

                              q.add(temp.right);

                          size--;

                   }

             }

             return (oddSum - evenSum);  

      }

  

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

      public static void main(String args[])

      {

             // построить дерево

             Node root = new Node(5);

             root.left = new Node(2);

             root.right = new Node(6);

             root.left.left = new Node(1);

             root.left.right = new Node(4);

             root.left.right.left = new Node(3);

             root.right.right = new Node(8);

             root.right.right.right = new Node(9);

             root.right.right.left = new Node(7);

  

             System.out.println("diffence between sums is "

                                evenOddLevelDifference(root));

      }

}
// Этот код предоставлен rachana soma

python3

# Python3 программа для поиска максимального продукта
# уровня в двоичном дереве

  
# Вспомогательная функция, которая выделяет новый
# узел с заданными данными и None
# левый и правый пиры

class newNode: 

  

    # Конструкция для создания нового узла

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
# вернуть разницу сумм нечетных
# уровень и даже уровень

def evenOddLevelDifference(root):

  

    if (not root):

        return 0

  

    # создать очередь для

    # уровень порядка обхода

    q = []

    q.append(root)

  

    level = 0

    evenSum = 0

    oddSum = 0

  

    # ход, пока очередь не пуста

    while (len(q)): 

      

        size = len(q)

        level += 1

  

        # ход за полный уровень

        while(size > 0):

          

            temp = q[0] #.фронт()

            q.pop(0)

  

            # проверить, если уровень нет. четный или

            # нечетное и соответственно обновление

            # EvenSum или OddSum

            if(level % 2 == 0):

                evenSum += temp.data

            else:

                oddSum += temp.data

          

            # проверить левого ребенка

            if (temp.left) :

              

                q.append(temp.left)

              

            # проверить правильность ребенка

            if (temp.right):

              

                q.append(temp.right)

              

            size -= 1

          

    return (oddSum - evenSum)

  
Код водителя

if __name__ == '__main__':

      

    «»»

    Давайте создадим двоичное дерево, показанное

    в приведенном выше примере "" "

    root = newNode(5)

    root.left = newNode(2)

    root.right = newNode(6)

    root.left.left = newNode(1)

    root.left.right = newNode(4)

    root.left.right.left = newNode(3)

    root.right.right = newNode(8)

    root.right.right.right = newNode(9)

    root.right.right.left = newNode(7)

  

    result = evenOddLevelDifference(root)

    print("Diffence between sums is", result)

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// C # программа для поиска
// разница между
// суммы нечетного уровня
// и даже узлы уровня
// двоичного дерева

using System;

using System.Collections.Generic;

  
// Пользовательский класс узла

public class Node

{

    public int data;

    public Node left, right;

          

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

    public Node(int key) 

    {

        data = key;

        left = right = null;

    }

}

  

public class GFG 

{

    // вернуть разницу

    // суммы нечетного уровня и четного уровня

    static int evenOddLevelDifference(Node root)

    {

            if (root == null)

                return 0;

  

            // создаем очередь для

            // уровень прохождения заказа

            Queue<Node> q = new Queue<Node>();

            q.Enqueue(root);

  

            int level = 0; 

            int evenSum = 0, oddSum = 0;

  

            // пройти до

            // очередь пуста

            while (q.Count != 0) 

            {

                int size = q.Count;

                level++;

                      

                // пройти полный уровень

                while (size > 0)

                {

                        Node temp = q.Dequeue();

  

                        // проверить, если уровень нет.

                        // четный или нечетный и

                        // соответственно обновляем

                        // EvenSum или OddSum

                        if (level % 2 == 0)

                            evenSum += temp.data;

                        else

                            oddSum += temp.data;

  

                        // проверка левого ребенка

                        if (temp.left != null)

                            q.Enqueue(temp.left);

                              

                        // проверка на правильность ребенка

                        if (temp.right != null)

                            q.Enqueue(temp.right);

                        size--;

                }

            }

            return (oddSum - evenSum); 

    }

  

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

    public static void Main(String []args)

    {

            // построить дерево

            Node root = new Node(5);

            root.left = new Node(2);

            root.right = new Node(6);

            root.left.left = new Node(1);

            root.left.right = new Node(4);

            root.left.right.left = new Node(3);

            root.right.right = new Node(8);

            root.right.right.right = new Node(9);

            root.right.right.left = new Node(7);

  

            Console.WriteLine("diffence between sums is "

                                evenOddLevelDifference(root));

    }

}

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


Выход:

diffence between sums is -9

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

Ниже приведена реализация этого подхода.

C ++

// Рекурсивная программа для поиска различий
// между суммой узлов на нечетном уровне
// и сумма на четном уровне
#include <bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

class node 

    public:

    int data; 

    node* left, *right; 

}; 

  
// Сервисная функция для выделения
// новый узел дерева с данными

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = Node->right = NULL; 

    return (Node); 

  
// Основная функция, которая возвращает
// разница между нечетным и четным
// узлы уровня

int getLevelDiff(node *root) 


// Базовый вариант

if (root == NULL) 

        return 0; 

  
// Разница для root - это данные root - разница для
// левое поддерево - разница для правого поддерева

return root->data - getLevelDiff(root->left) - 

                    getLevelDiff(root->right); 

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

int main() 

    node *root = newNode(5); 

    root->left = newNode(2); 

    root->right = newNode(6); 

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

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

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

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

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

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

    cout<<getLevelDiff(root)<<" is the required difference\n"

    return 0; 

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

С

// Рекурсивная программа для поиска разницы между суммой узлов в
// нечетный уровень и сумма на четном уровне
#include <stdio.h>
#include <stdlib.h>

  
// Узел двоичного дерева

struct node

{

    int data;

    struct node* left, *right;

};

  
// Вспомогательная функция для выделения нового узла дерева с данными

struct node* newNode(int data)

{

    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->data = data;

    node->left =  node->right = NULL;

    return (node);

}

  
// Основная функция, которая возвращает разницу между нечетным и четным уровнем
// узлы

int getLevelDiff(struct node *root)

{

   // Базовый вариант

   if (root == NULL)

         return 0;

  

   // Разница для root - это данные root - разница для

   // левое поддерево - разница для правого поддерева

   return root->data - getLevelDiff(root->left) - 

                                         getLevelDiff(root->right);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct node *root = newNode(5);

    root->left = newNode(2);

    root->right = newNode(6);

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

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

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

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

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

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

    printf("%d is the required difference\n", getLevelDiff(root));

    getchar();

    return 0;

}

Джава

// Рекурсивная Java-программа для поиска разницы между суммой узлов в
// нечетный уровень и сумма на четном уровне

   
// Узел двоичного дерева

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right;

    }

}

   

class BinaryTree 

{

    // Основная функция, которая возвращает разницу между нечетным и четным уровнем

    // узлы

    Node root;

   

    int getLevelDiff(Node node) 

    {

        // Базовый вариант

        if (node == null)

            return 0;

  

        // Разница для root - это данные root - разница для

        // левое поддерево - разница для правого поддерева

        return node.data - getLevelDiff(node.left) - 

                                              getLevelDiff(node.right);

    }

   

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(5);

        tree.root.left = new Node(2);

        tree.root.right = new Node(6);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(4);

        tree.root.left.right.left = new Node(3);

        tree.root.right.right = new Node(8);

        tree.root.right.right.right = new Node(9);

        tree.root.right.right.left = new Node(7);

        System.out.println(tree.getLevelDiff(tree.root) +  

                                             " is the required difference");

   

    }

}

   
// Этот код предоставлен Mayank Jaiswal

питон

# Рекурсивная программа для поиска разницы между суммой узлов
# на нечетном уровне и сумма на четном уровне

  
# Узел двоичного дерева

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Основная функция, которая возвращает разницу между нечетным и
# четные узлы уровня

def getLevelDiff(root):

  

    # Базовый вариант

    if root is None:

        return 0 

  

    # Разница для root - это данные root - разница для

    # левое поддерево - разница для правого поддерева

    return (root.data - getLevelDiff(root.left)- 

        getLevelDiff(root.right))

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(5)

root.left = Node(2)

root.right = Node(6)

root.left.left = Node(1)

root.left.right = Node(4)

root.left.right.left = Node(3)

root.right.right = Node(8)

root.right.right.right = Node(9)

root.right.right.left = Node(7)

print "%d is the required difference" %(getLevelDiff(root))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// Рекурсивная программа на C # для поиска
// разница между суммой узлов при
// нечетный уровень и сумма на четном уровне

  
// Узел двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right;

    }

}

  

public class BinaryTree

{

    // Основная функция, возвращающая разницу

    // между нечетными и четными узлами уровня

    public Node root;

  

    public virtual int getLevelDiff(Node node)

    {

        // Базовый вариант

        if (node == null)

        {

            return 0;

        }

  

        // Разница для root - это root

        // data - разница для левого поддерева

        // - разница для правого поддерева

        return node.data - getLevelDiff(node.left)

                        - getLevelDiff(node.right);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(5);

        tree.root.left = new Node(2);

        tree.root.right = new Node(6);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(4);

        tree.root.left.right.left = new Node(3);

        tree.root.right.right = new Node(8);

        tree.root.right.right.right = new Node(9);

        tree.root.right.right.left = new Node(7);

        Console.WriteLine(tree.getLevelDiff(tree.root)

                        + " is the required difference");

  

    }

}

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


Выход:

-9 is the required difference

Временная сложность обоих методов составляет O (n), но второй метод прост и легко реализуем.

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

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

Разница между суммами нечетного уровня и четных узлов уровня двоичного дерева

0.00 (0%) 0 votes