Итерационный подход к проверке свойства дочерней суммы в двоичном дереве
Опубликовано: 23 Января, 2022
Для двоичного дерева напишите функцию, которая возвращает истину, если дерево удовлетворяет следующему свойству:
Для каждого узла значение данных должно быть равно сумме значений данных в левом и правом потомках. Считайте значение данных 0 для потомков NULL.
Примеры:
Вход :
10
/
8 2
/
3 5 2
Выход: Да
Вход :
5
/
-2 7
/
1 6 7
Выход: Нет
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Мы уже обсуждали рекурсивный подход. В этом посте обсуждается итеративный подход.
Подход: идея состоит в том, чтобы использовать очередь для обхода порядка уровней двоичного дерева и одновременной проверки каждого узла:
- Если текущий узел имеет двух дочерних элементов и если текущий узел равен сумме его левого и правого дочерних элементов.
- Если текущий узел только что оставил дочерний элемент и если текущий узел равен своему левому дочернему элементу.
- Если у текущего узла есть только правильный дочерний элемент и если текущий узел равен своему правому дочернему элементу.
Below is the implementation of the above approach:
C++
// C++ program to check children sum property#include <bits/stdc++.h>using namespace std; // A binary tree nodestruct Node { int data; Node *left, *right;}; // Utility function to allocate memory for a new nodeNode* newNode(int data){ Node* node = new (Node); node->data = data; node->left = node->right = NULL; return (node);} // Function to check if the tree holds// children sum propertybool CheckChildrenSum(Node* root){ queue<Node*> q; // Push the root node q.push(root); while (!q.empty()) { Node* temp = q.front(); q.pop(); // If the current node has both left and right children if (temp->left && temp->right) { // If the current node is not equal to // the sum of its left and right children // return false if (temp->data != temp->left->data + temp->right->data) return false; q.push(temp->left); q.push(temp->right); } // If the current node has right child else if (!temp->left && temp->right) { // If the current node is not equal to // its right child return false if (temp->data != temp->right->data) return false; q.push(temp->right); } // If the current node has left child else if (!temp->right && temp->left) { // If the current node is not equal to // its left child return false if (temp->data != temp->left->data) return false; q.push(temp->left); } } // If the given tree has children // sum property return true return true;} // Driver codeint main(){ Node* root = newNode(10); root->left = newNode(8); root->right = newNode(2); root->left->left = newNode(3); root->left->right = newNode(5); root->right->right = newNode(2); if (CheckChildrenSum(root)) printf("Yes"); else printf("No"); return 0;} |
Java
// Java program to check children sum property import java.util.*;class GFG{ // A binary tree node static class Node { int data; Node left, right; } // Utility function to allocate memory for a new node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Function to check if the tree holds // children sum property static boolean CheckChildrenSum(Node root) { Queue<Node> q = new LinkedList<Node>(); // add the root node q.add(root); while (q.size() > 0) { Node temp = q.peek(); q.remove(); // If the current node has both left and right children if (temp.left != null && temp.right != null) { // If the current node is not equal to // the sum of its left and right children // return false if (temp.data != temp.left.data + temp.right.data) return false; q.add(temp.left); q.add(temp.right); } // If the current node has right child else if (temp.left == null && temp.right != null) { // If the current node is not equal to // its right child return false if (temp.data != temp.right.data) return false; q.add(temp.right); } // If the current node has left child else if (temp.right == null && temp.left != null) { // If the current node is not equal to // its left child return false if (temp.data != temp.left.data) return false; q.add(temp.left); } } // If the given tree has children // sum property return true return true; } // Driver code public static void main(String args[]){ Node root = newNode(10); root.left = newNode(8); root.right = newNode(2); root.left.left = newNode(3); root.left.right = newNode(5); root.right.right = newNode(2); if (CheckChildrenSum(root)) System.out.printf("Yes"); else System.out.printf("No"); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 program to check # children sum property # A binary tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to check if the tree holds # children sum property def CheckChildrenSum(root): q = [] # Push the root node q.append(root) while len(q) != 0: temp = q.pop() # If the current node has both # left and right children if temp.left and temp.right: # If the current node is not equal # to the sum of its left and right # children, return false if (temp.data != temp.left.data + temp.right.data): return False q.append(temp.left) q.append(temp.right) # If the current node has right child elif not temp.left and temp.right: # If the current node is not equal # to its right child return false if temp.data != temp.right.data: return False q.append(temp.right) # If the current node has left child elif not temp.right and temp.left: # If the current node is not equal # to its left child return false if temp.data != temp.left.data: return False q.append(temp.left) # If the given tree has children # sum property return true return True # Driver code if __name__ == "__main__": root = Node(10) root.left = Node(8) root.right = Node(2) root.left.left = Node(3) root.left.right = Node(5) root.right.right = Node(2) if CheckChildrenSum(root): print("Yes") else: print("No") # This code is contributed # by Rituraj Jain |
C#
// C# program to check children sum property using System;using System.Collections.Generic; class GFG { // A binary tree node public class Node { public int data; public Node left, right; } // Utility function to allocate// memory for a new node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Function to check if the tree holds // children sum property static Boolean CheckChildrenSum(Node root) { Queue<Node> q = new Queue<Node>(); // add the root node q.Enqueue(root); while (q.Count > 0) { Node temp = q.Peek(); q.Dequeue(); // If the current node has both // left and right children if (temp.left != null && temp.right != null) { // If the current node is not equal to // the sum of its left and right children // return false if (temp.data != temp.left.data + temp.right.data) return false; q.Enqueue(temp.left); q.Enqueue(temp.right); } // If the current node has right child else if (temp.left == null && temp.right != null) { // If the current node is not equal to // its right child return false if (temp.data != temp.right.data) return false; q.Enqueue(temp.right); } // If the current node has left child else if (temp.right == null && temp.left != null) { // If the current node is not equal to // its left child return false if (temp.data != temp.left.data) return false; q.Enqueue(temp.left); } } // If the given tree has children // sum property return true return true; } // Driver code public static void Main(String []args) { Node root = newNode(10); root.left = newNode(8); root.right = newNode(2); root.left.left = newNode(3); root.left.right = newNode(5); root.right.right = newNode(2); if (CheckChildrenSum(root)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by Rajput-Ji |
Output:
Yes
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.