Dado un árbol binario , la tarea es encontrar la suma de todos los Nodes especialmente balanceados en el árbol binario dado.
Un Node especialmente equilibrado en un árbol binario contiene la suma de los Nodes de un subárbol (ya sea izquierdo o derecho) como par y la suma del otro subárbol como impar.
Los Nodes que tienen un solo hijo o ningún hijo nunca pueden ser un Node equilibrado.
Ejemplos:
Entrada: A continuación se muestra el árbol dado:
Salida: 33
Explicación:
Los Nodes especialmente balanceados son 11 y 22.
Para el Node 11:
La suma del subárbol izquierdo es (23 + 13 + 9) = 45 que es impar.
La suma del subárbol derecho es (44 + 22 + 7 + 6 + 15) = 94 que es Par.
Para el Node 22:
la suma del subárbol izquierdo es 6, que es par.
La suma del subárbol derecho es 15, que es impar.
Por lo tanto, la suma de los Nodes especialmente equilibrados es 11 + 22 = 33.Entrada: A continuación se muestra el árbol dado:
Salida: 16
Explicación:
los Nodes especialmente equilibrados son 4 y 12.
Para el Node 4:
la suma del subárbol izquierdo es 2, que es par.
La suma del subárbol derecho es 3, que es impar.
Para el Node 12:
la suma del subárbol izquierdo es 17, que es impar.
La suma del subárbol derecho es (16 + 4 + 9 + 2 + 3) = 34 que es Par.
Por lo tanto, la suma de los Nodes especialmente equilibrados es 4 + 12 = 16.
Enfoque: la idea es realizar DFS Traversal en el árbol dado usando recursividad y actualizar la suma final según las condiciones dadas. Siga los pasos a continuación:
- Inicialice un totalSum como 0 que almacena la suma de todos los Nodes especialmente equilibrados.
- Realice el DFS Traversal en el árbol dado y verifique lo siguiente:
- Si el Node es un Node hoja , devuelva el valor de ese Node.
- Ahora, si el Node actual no es un Node hoja, recorra recursivamente el subárbol izquierdo y derecho.
- Devuelve el valor de la suma del subárbol izquierdo y derecho con el valor raíz actual cuando finaliza cada llamada recursiva.
- Compruebe si las sumas devueltas satisfacen la propiedad del Node especialmente equilibrado. SI se encuentra que es cierto, agregue el valor del Node actual a totalSum .
- Imprima el valor de totalSum después de completar los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Binary Tree
struct Node {
int data;
Node *left, *right;
};
// Function to create a new node
Node* newnode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
// Return the created node
return temp;
}
// Function to insert a node in the tree
Node* insert(string s, int i, int N,
Node* root, Node* temp)
{
if (i == N)
return temp;
// Left insertion
if (s[i] == 'L')
root->left = insert(s, i + 1, N,
root->left,
temp);
// Right insertion
else
root->right = insert(s, i + 1, N,
root->right,
temp);
// Return the root node
return root;
}
// Function to find sum of specially
// balanced nodes in the Tree
int SBTUtil(Node* root, int& sum)
{
// Base Case
if (root == NULL)
return 0;
if (root->left == NULL
&& root->right == NULL)
return root->data;
// Find the left subtree sum
int left = SBTUtil(root->left, sum);
// Find the right subtree sum
int right = SBTUtil(root->right, sum);
// Condition of specially
// balanced node
if (root->left && root->right) {
// Condition of specially
// balanced node
if ((left % 2 == 0
&& right % 2 != 0)
|| (left % 2 != 0
&& right % 2 == 0)) {
sum += root->data;
}
}
// Return the sum
return left + right + root->data;
}
// Function to build the binary tree
Node* build_tree(int R, int N,
string str[],
int values[])
{
// Form root node of the tree
Node* root = newnode(R);
int i;
// Insert nodes into tree
for (i = 0; i < N - 1; i++) {
string s = str[i];
int x = values[i];
// Create a new Node
Node* temp = newnode(x);
// Insert the node
root = insert(s, 0, s.size(),
root, temp);
}
// Return the root of the Tree
return root;
}
// Function to find the sum of specially
// balanced nodes
void speciallyBalancedNodes(
int R, int N, string str[], int values[])
{
// Build Tree
Node* root = build_tree(R, N,
str, values);
// Stores the sum of specially
// balanced node
int sum = 0;
// Function Call
SBTUtil(root, sum);
// Print required sum
cout << sum << " ";
}
// Driver Code
int main()
{
// Given nodes
int N = 7;
// Given root
int R = 12;
// Given path info of nodes
// from root
string str[N - 1]
= { "L", "R", "RL",
"RR", "RLL", "RLR" };
// Given node values
int values[N - 1] = { 17, 16, 4,
9, 2, 3 };
// Function Call
speciallyBalancedNodes(R, N, str,
values);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
static int sum;
//Structure of Binary Tree
static class Node
{
int data;
Node left, right;
};
//Function to create a new node
static Node newnode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
// Return the created node
return temp;
}
//Function to insert a node in the tree
static Node insert(String s, int i, int N,
Node root, Node temp)
{
if (i == N)
return temp;
// Left insertion
if (s.charAt(i) == 'L')
root.left = insert(s, i + 1, N,
root.left, temp);
// Right insertion
else
root.right = insert(s, i + 1, N,
root.right, temp);
// Return the root node
return root;
}
//Function to find sum of specially
//balanced nodes in the Tree
static int SBTUtil(Node root)
{
// Base Case
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
return root.data;
// Find the left subtree sum
int left = SBTUtil(root.left);
// Find the right subtree sum
int right = SBTUtil(root.right);
// Condition of specially
// balanced node
if (root.left != null &&
root.right != null)
{
// Condition of specially
// balanced node
if ((left % 2 == 0 && right % 2 != 0) ||
(left % 2 != 0 && right % 2 == 0))
{
sum += root.data;
}
}
// Return the sum
return left + right + root.data;
}
//Function to build the binary tree
static Node build_tree(int R, int N,
String str[],
int values[])
{
// Form root node of the tree
Node root = newnode(R);
int i;
// Insert nodes into tree
for (i = 0; i < N - 1; i++)
{
String s = str[i];
int x = values[i];
// Create a new Node
Node temp = newnode(x);
// Insert the node
root = insert(s, 0, s.length(),
root, temp);
}
// Return the root of the Tree
return root;
}
// Function to find the
// sum of specially
// balanced nodes
static void speciallyBalancedNodes(int R, int N,
String str[],
int values[])
{
// Build Tree
Node root = build_tree(R, N, str,
values);
// Stores the sum of specially
// balanced node
sum = 0;
// Function Call
SBTUtil(root);
// Print required sum
System.out.print(sum + " ");
}
//Driver Code
public static void main(String[] args)
{
// Given nodes
int N = 7;
// Given root
int R = 12;
// Given path info of nodes
// from root
String str[] = {"L", "R", "RL",
"RR", "RLL", "RLR"};
// Given node values
int values[] = {17, 16, 4,
9, 2, 3};
// Function Call
speciallyBalancedNodes(R, N, str,
values);
}
}
//This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Structure of Binary Tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to create a new node def newnode(data): temp = Node(data) # Return the created node return temp # Function to insert a node in the tree def insert(s, i, N, root, temp): if (i == N): return temp # Left insertion if (s[i] == 'L'): root.left = insert(s, i + 1, N, root.left, temp) # Right insertion else: root.right = insert(s, i + 1, N, root.right, temp) # Return the root node return root # Function to find sum of specially # balanced nodes in the Tree def SBTUtil(root, sum): # Base Case if (root == None): return [0, sum] if (root.left == None and root.right == None): return [root.data, sum] # Find the left subtree sum left, sum = SBTUtil(root.left, sum) # Find the right subtree sum right, sum = SBTUtil(root.right, sum) # Condition of specially # balanced node if (root.left and root.right): # Condition of specially # balanced node if ((left % 2 == 0 and right % 2 != 0) or (left % 2 != 0 and right % 2 == 0)): sum += root.data # Return the sum return [left + right + root.data, sum] # Function to build the binary tree def build_tree(R, N, str, values): # Form root node of the tree root = newnode(R) # Insert nodes into tree for i in range(0, N - 1): s = str[i] x = values[i] # Create a new Node temp = newnode(x) # Insert the node root = insert(s, 0, len(s), root, temp) # Return the root of the Tree return root # Function to find the sum of specially # balanced nodes def speciallyBalancedNodes(R, N, str, values): # Build Tree root = build_tree(R, N, str, values) # Stores the sum of specially # balanced node sum = 0 # Function Call tmp, sum = SBTUtil(root, sum) # Print required sum print(sum, end = ' ') # Driver code if __name__ == "__main__": # Given nodes N = 7 # Given root R = 12 # Given path info of nodes # from root str = [ "L", "R", "RL", "RR", "RLL", "RLR" ] # Given node values values = [ 17, 16, 4, 9, 2, 3 ] # Function Call speciallyBalancedNodes(R, N, str, values) # This code is contributed by rutvik_56
C#
//C# program for
// the above approach
using System;
class GFG{
static int sum;
//Structure of Binary Tree
class Node
{
public int data;
public Node left, right;
};
//Function to create a new node
static Node newnode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
// Return the created node
return temp;
}
//Function to insert a node in the tree
static Node insert(String s, int i, int N,
Node root, Node temp)
{
if (i == N)
return temp;
// Left insertion
if (s[i] == 'L')
root.left = insert(s, i + 1, N,
root.left, temp);
// Right insertion
else
root.right = insert(s, i + 1, N,
root.right, temp);
// Return the root node
return root;
}
//Function to find sum of specially
//balanced nodes in the Tree
static int SBTUtil(Node root)
{
// Base Case
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
return root.data;
// Find the left subtree sum
int left = SBTUtil(root.left);
// Find the right subtree sum
int right = SBTUtil(root.right);
// Condition of specially
// balanced node
if (root.left != null &&
root.right != null)
{
// Condition of specially
// balanced node
if ((left % 2 == 0 && right % 2 != 0) ||
(left % 2 != 0 && right % 2 == 0))
{
sum += root.data;
}
}
// Return the sum
return left + right + root.data;
}
//Function to build the binary tree
static Node build_tree(int R, int N,
String []str,
int []values)
{
// Form root node of the tree
Node root = newnode(R);
int i;
// Insert nodes into tree
for (i = 0; i < N - 1; i++)
{
String s = str[i];
int x = values[i];
// Create a new Node
Node temp = newnode(x);
// Insert the node
root = insert(s, 0, s.Length,
root, temp);
}
// Return the root of the Tree
return root;
}
// Function to find the
// sum of specially
// balanced nodes
static void speciallyBalancedNodes(int R, int N,
String []str,
int []values)
{
// Build Tree
Node root = build_tree(R, N, str,
values);
// Stores the sum of specially
// balanced node
sum = 0;
// Function Call
SBTUtil(root);
// Print required sum
Console.Write(sum + " ");
}
//Driver Code
public static void Main(String[] args)
{
// Given nodes
int N = 7;
// Given root
int R = 12;
// Given path info of nodes
// from root
String []str = {"L", "R", "RL",
"RR", "RLL", "RLR"};
// Given node values
int []values = {17, 16, 4,
9, 2, 3};
// Function Call
speciallyBalancedNodes(R, N, str,
values);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let sum;
// Structure of Binary Tree
class Node
{
constructor(data)
{
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to create a new node
function newnode(data)
{
let temp = new Node(data);
// Return the created node
return temp;
}
// Function to insert a node in the tree
function insert(s, i, N, root, temp)
{
if (i == N)
return temp;
// Left insertion
if (s[i] == 'L')
root.left = insert(s, i + 1, N,
root.left, temp);
// Right insertion
else
root.right = insert(s, i + 1, N,
root.right, temp);
// Return the root node
return root;
}
// Function to find sum of specially
// balanced nodes in the Tree
function SBTUtil(root)
{
// Base Case
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
return root.data;
// Find the left subtree sum
let left = SBTUtil(root.left);
// Find the right subtree sum
let right = SBTUtil(root.right);
// Condition of specially
// balanced node
if (root.left != null &&
root.right != null)
{
// Condition of specially
// balanced node
if ((left % 2 == 0 && right % 2 != 0) ||
(left % 2 != 0 && right % 2 == 0))
{
sum += root.data;
}
}
// Return the sum
return left + right + root.data;
}
// Function to build the binary tree
function build_tree(R, N, str, values)
{
// Form root node of the tree
let root = newnode(R);
let i;
// Insert nodes into tree
for(i = 0; i < N - 1; i++)
{
let s = str[i];
let x = values[i];
// Create a new Node
let temp = newnode(x);
// Insert the node
root = insert(s, 0, s.length,
root, temp);
}
// Return the root of the Tree
return root;
}
// Function to find the
// sum of specially
// balanced nodes
function speciallyBalancedNodes(R, N, str, values)
{
// Build Tree
let root = build_tree(R, N, str, values);
// Stores the sum of specially
// balanced node
sum = 0;
// Function Call
SBTUtil(root);
// Print required sum
document.write(sum + " ");
}
// Driver code
// Given nodes
let N = 7;
// Given root
let R = 12;
// Given path info of nodes
// from root
let str = [ "L", "R", "RL",
"RR", "RLL", "RLR" ];
// Given node values
let values = [ 17, 16, 4, 9, 2, 3 ];
// Function Call
speciallyBalancedNodes(R, N, str, values);
// This code is contributed by suresh07
</script>
Producción:
16
Complejidad temporal: O(N)
Espacio auxiliar: O(N)