Подсчитайте все тройни бабушек, дедушек-родителей-потомков в двоичном дереве, сумма которых больше X
Опубликовано: 15 Января, 2022
Учитывая целое число X и двоичное дерево, задача состоит в том, чтобы подсчитать количество триплетов триплетов узлов таким образом, чтобы их сумма была больше, чем X, и у них были отношения дедушка-дедушка -> родитель -> потомок.
Пример:
Ввод: X = 100
10
/
1 22
/ /
35 4 15 67
/ / / /
57 38 9 10 110 312 131 414
/
8 39
Выход: 6
Это тройня:
22 -> 15 -> 110
22 -> 15 -> 312
15 -> 312 -> 8
22 -> 67 -> 131
22 -> 67 -> 414
67 -> 414 -> 39
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: проблема может быть решена с использованием метода скользящего суммирования с плавающим периодом, равным 3 (дедушка или бабушка -> родитель -> потомок).
- Пройдите по дереву в предзаказе или постзаказе (НЕЗАКАЗ НЕ РАБОТАЕТ)
- Поддерживайте стек, в котором мы поддерживаем скользящую сумму с периодом вращения как 3
- Когда в стеке больше 3 элементов и если самое верхнее значение больше X, мы увеличиваем результат на 1.
- Когда мы перемещаемся вверх по дереву рекурсии, мы выполняем операцию POP со стеком, чтобы все скользящие суммы нижних уровней удалялись из стека.
Ниже представлена реализация описанного выше подхода:
Эффективный подход: проблема может быть решена путем сохранения трех переменных, которые называются дедушка и бабушка, родитель и ребенок. Это можно сделать в постоянном пространстве без использования других структур данных.
- Пройдите по дереву в предзаказе
- Поддерживайте 3 переменные: grandParent, parent и child.
- Всякий раз, когда у нас есть сумма, превышающая цель, мы можем увеличить счет или вывести тройку.
Below is the implementation of the above approach:
C++
// CPP implementation to print// the nodes having a single child#include <bits/stdc++.h>using namespace std;// Class of the Binary Tree nodestruct Node{ int data; Node *left, *right; Node(int x) { data = x; left = right = NULL; }};// global variableint cont = 0;void preorder(Node* grandParent, Node* parent, Node* child, int sum){ if(grandParent != NULL && parent != NULL && child != NULL && (grandParent -> data + parent -> data + child->data) > sum) { cont++; //uncomment below lines if you // want to print triplets /*System->out->print(grandParent ->data+"-->"+parent->data+"--> "+child->data); System->out->println();*/ } if(child == NULL) return; preorder(parent, child, child -> left, sum); preorder(parent, child, child -> right, sum);}//Driver codeint main(){ Node *r10 = new Node(10); Node *r1 = new Node(1); Node *r22 = new Node(22); Node *r35 = new Node(35); Node *r4 = new Node(4); Node *r15 = new Node(15); Node *r67 = new Node(67); Node *r57 = new Node(57); Node *r38 = new Node(38); Node *r9 = new Node(9); Node *r10_2 = new Node(10); Node *r110 = new Node(110); Node *r312 = new Node(312); Node *r131 = new Node(131); Node *r414 = new Node(414); Node *r8 = new Node(8); Node *r39 = new Node(39); r10 -> left = r1; r10 -> right = r22; r1 -> left = r35; r1 -> right = r4; r22 -> left = r15; r22 -> right = r67; r35 -> left = r57; r35 -> right = r38; r4 -> left = r9; r4 -> right = r10_2; r15 -> left = r110; r15 -> right = r312; r67 -> left = r131; r67 -> right = r414; r312 -> left = r8; r414 -> right = r39; preorder(NULL, NULL, r10, 100); cout << cont;}// This code is contributed by Mohit Kumar 29 |
Java
class Node{ int data; Node left; Node right; public Node(int data) { this.data=data; }} class TreeTriplet { static int count=0; // global variable public void preorder(Node grandParent,Node parent,Node child,int sum) { if(grandParent!=null && parent!=null && child!=null && (grandParent.data+parent.data+child.data) > sum) { count++; //uncomment below lines if you want to print triplets /*System.out.print(grandParent.data+"-->"+parent.data+"-->"+child.data); System.out.println();*/ } if(child==null) return; preorder(parent,child,child.left,sum); preorder(parent,child,child.right,sum); } public static void main(String args[]) { Node r10 = new Node(10); Node r1 = new Node(1); Node r22 = new Node(22); Node r35 = new Node(35); Node r4 = new Node(4); Node r15 = new Node(15); Node r67 = new Node(67); Node r57 = new Node(57); Node r38 = new Node(38); Node r9 = new Node(9); Node r10_2 = new Node(10); Node r110 = new Node(110); Node r312 = new Node(312); Node r131 = new Node(131); Node r414 = new Node(414); Node r8 = new Node(8); Node r39 = new Node(39); r10.left=r1; r10.right=r22; r1.left=r35; r1.right=r4; r22.left=r15; r22.right=r67; r35.left=r57; r35.right=r38; r4.left=r9; r4.right=r10_2; r15.left=r110; r15.right=r312; r67.left=r131; r67.right=r414; r312.left=r8; r414.right=r39; TreeTriplet p = new TreeTriplet(); p.preorder(null, null, r10,100); System.out.println(count);} } // This code is contributed by Akshay Siddhpura |
Python
# Python3 program to implement# the above approachclass Node: def __init__(self, data): self.left = None self.right = None self.data = data # global variablecount = 0 def preorder(grandParent, parent, child, sum): global count if(grandParent != None and parent != None and child != None and (grandParent.data + parent.data + child.data) > sum): count += 1 # uncomment below lines if # you want to print triplets # System.out.print(grandParent. # data+"-->"+parent.data+"--> # "+child.data); System.out.println(); if(child == None): return; preorder(parent, child, child.left, sum); preorder(parent, child, child.right, sum); # Driver codeif __name__ == "__main__": r10 = Node(10); r1 = Node(1); r22 = Node(22); r35 = Node(35); r4 = Node(4); r15 = Node(15); r67 = Node(67); r57 = Node(57); r38 = Node(38); r9 = Node(9); r10_2 = Node(10); r110 = Node(110); r312 = Node(312); r131 = Node(131); r414 = Node(414); r8 = Node(8); r39 = Node(39); r10.left = r1; r10.right = r22; r1.left = r35; r1.right = r4; r22.left = r15; r22.right = r67; r35.left = r57; r35.right = r38; r4.left = r9; r4.right = r10_2; r15.left = r110; r15.right = r312; r67.left = r131; r67.right = r414; r312.left = r8; r414.right = r39; preorder(None, None, r10, 100) print(count); # This code is contributed by Rutvik_56 |
C#
// C# program to find an index which has// same number of even elements on left and// right, Or same number of odd elements on// left and right.using System; public class Node{ public int data; public Node left; public Node right; public Node(int data) { this.data = data; }}class GFG{ static int count = 0; // global variable public void preorder(Node grandParent, Node parent, Node child, int sum) { if(grandParent != null && parent != null && child != null && (grandParent.data + parent.data + child.data) > sum) { count++; // uncomment below lines if you want to print triplets /*System.out.print(grandParent.data+"-->"+parent.data+"-->"+child.data); System.out.println();*/ } if(child == null) return; preorder(parent,child,child.left,sum); preorder(parent,child,child.right,sum); } // Driver Code public static void Main(String []args) { Node r10 = new Node(10); Node r1 = new Node(1); Node r22 = new Node(22); Node r35 = new Node(35); Node r4 = new Node(4); Node r15 = new Node(15); Node r67 = new Node(67); Node r57 = new Node(57); Node r38 = new Node(38); Node r9 = new Node(9); Node r10_2 = new Node(10); Node r110 = new Node(110); Node r312 = new Node(312); Node r131 = new Node(131); Node r414 = new Node(414); Node r8 = new Node(8); Node r39 = new Node(39); r10.left = r1; r10.right = r22; r1.left = r35; r1.right = r4; r22.left = r15; r22.right = r67; r35.left = r57; r35.right = r38; r4.left = r9; r4.right = r10_2; r15.left = r110; r15.right = r312; r67.left = r131; r67.right = r414; r312.left = r8; r414.right = r39; GFG p = new GFG(); p.preorder(null, null, r10,100); Console.WriteLine(count);}}// This code is contributed by 29AjayKumar |
Output:
6
Сложность времени: O (n)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.