Разница между суммой четных и нечетных узлов в двоичном дереве
Опубликовано: 9 Января, 2022
Для двоичного дерева задача состоит в том, чтобы найти абсолютную разницу между четными и нечетными узлами в двоичном дереве.
Примеры:
Вход:
5
/
2 6
/
1 4 8
/ /
3 7 9
Выход: 5
Объяснение:
Сумма узлов с нечетным значением:
5 + 1 + 3 + 7 + 9 = 25
Сумма узлов четных значений:
2 + 6 + 4 + 8 = 20
Абсолютная разница = (25-20) = 5.
Вход:
4
/
1 4
/
7 2 6
Выход: 8
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход:
Выполните следующие действия, чтобы решить проблему:
- Просмотрите каждый узел в дереве и проверьте, является ли значение в этом узле нечетным или четным.
- Обновите oddSum и evenSum соответственно после посещения каждого узла.
- После полного обхода дерева выведите абсолютную разницу между oddSum и evenSum .
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;int oddsum = 0;int evensum = 0;int ans = 0;struct node { int data; struct node* left; struct node* right;};struct node* newnode(int data){ node* temp = new node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Function calculate the sum of// odd and even value nodevoid OddEvenDifference(struct node* root){ // If root is NULL if (root == NULL) { return; } else { // Check if current root // is odd or even if (root->data % 2 == 0) { evensum += root->data; } else { oddsum += root->data; } // Call on the left subtree OddEvenDifference(root->left); // Call on the right subtree OddEvenDifference(root->right); }}// Driver Codeint 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); OddEvenDifference(root); cout << abs(oddsum - evensum) << endl;} |
Java
// Java implementation of// the above approachclass GFG{static int oddsum = 0;static int evensum = 0;static int ans = 0;static class node{ int data; node left; node right;};static node newnode(int data){ node temp = new node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function calculate the sum of// odd and even value nodestatic void OddEvenDifference(node root){ // If root is null if (root == null) { return; } else { // Check if current root // is odd or even if (root.data % 2 == 0) { evensum += root.data; } else { oddsum += root.data; } // Call on the left subtree OddEvenDifference(root.left); // Call on the right subtree OddEvenDifference(root.right); }}// Driver Codepublic static void main(String[] args){ 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); OddEvenDifference(root); System.out.print(Math.abs( oddsum - evensum) + "
");}}// This code is contributed by amal kumar choubey |
Python3
# Python3 implementation of# the above approachoddsum = 0evensum = 0class Node: def __init__(self, data): self.left = None self.right = None self.data = data def newnode(data): temp = Node(data) return temp# Function calculate the sum of# odd and even value nodedef OddEvenDifference(root): global evensum, oddsum # If root is NULL if (root == None): return else: # Check if current root # is odd or even if (root.data % 2 == 0): evensum += root.data else: oddsum += root.data # Call on the left subtree OddEvenDifference(root.left) # Call on the right subtree OddEvenDifference(root.right) # Driver codeif __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) OddEvenDifference(root) print(abs(oddsum - evensum)) # This code is contributed by rutvik_56 |
C#
// C# implementation of// the above approachusing System;class GFG{static int oddsum = 0;static int evensum = 0;//static int ans = 0;class node{ public int data; public node left; public node right;};static node newnode(int data){ node temp = new node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function calculate the sum of// odd and even value nodestatic void OddEvenDifference(node root){ // If root is null if (root == null) { return; } else { // Check if current root // is odd or even if (root.data % 2 == 0) { evensum += root.data; } else { oddsum += root.data; } // Call on the left subtree OddEvenDifference(root.left); // Call on the right subtree OddEvenDifference(root.right); }}// Driver Codepublic static void Main(String[] args){ 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); OddEvenDifference(root); Console.Write(Math.Abs( oddsum - evensum) + "
");}}// This code is contributed by amal kumar choubey |
Output:
5
Сложность времени: O (N)
Вспомогательное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.