Dado un árbol binario que consta de N Nodes, la tarea es primero comprimir el árbol en diagonal para obtener una lista de enteros y luego comprimir nuevamente la lista para obtener un solo entero usando las siguientes operaciones:
- Cuando un árbol se comprime en diagonal, su valor en representación binaria se comprime.
- Considere cada posición de bit de cada valor de Node presente en una diagonal. Si una posición tiene S bits activados y NS bits no activados, establezca el bit para esa posición solo si S es mayor que NS . De lo contrario, desactive el bit para esa posición.
- Comprima cada diagonal para convertir el árbol en una lista. Luego, comprima cada elemento de la array en un solo entero usando el mismo proceso.
Ejemplo: si 7, 6, 3 y 4 se comprimen, entonces sus representaciones binarias, es decir, (111) 2 , (110) 2 , (011) 2 y (100) 2 se comprimen. Para la posición 0 , S ≤ NS y para las posiciones 1 y 2 , S > NS .
Por lo tanto, el número se convierte en (110) 2 = 6 .
Ejemplos:
Entrada: 6
/ \
5 3
/ \ / \
3 5 3 4
Salida: 3
Explicación:
Diagonal 1: Comprimir (6, 3, 4) = 6
Diagonal 2: Comprimir (5, 5, 3) = 5
Diagonal 3: Comprimir (3) = 3
Finalmente, comprima la lista (6, 5, 3) para obtener 7 .Entrada: 10
/ \
5 2
/ \
6 8
Salida: 2
Enfoque: La idea es usar un Hashmap para almacenar todos los Nodes que pertenecen a una diagonal particular del árbol. Siga los pasos a continuación para resolver el problema:
- Para el recorrido diagonal del árbol , realice un seguimiento de la distancia horizontal desde el Node raíz para cada Node.
- Usa un Hashmap para almacenar los elementos que pertenecen a la misma diagonal.
- Después del recorrido, cuente el número de bits establecidos para cada posición de cada diagonal del árbol y establezca el bit para las posiciones donde el número de bits establecidos excede el número de bits no establecidos.
- Almacene el valor comprimido de cada diagonal en una array .
- Después de obtener la array, aplique los mismos pasos de compresión para obtener el número entero requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
TreeNode *left,*right;
TreeNode(int v){
val = v;
left = NULL;
right = NULL;
}
};
// Function to compress the elements
// in an array into an integer
int findCompressValue(vector<int> arr){
int ans = 0;
int getBit = 1;
// Check for each bit position
for (int i = 0; i < 32; i++){
int S = 0;
int NS = 0;
for (int j:arr){
// Update the count of
// set and non-set bits
if (getBit & j)
S += 1;
else
NS += 1;
}
// If number of set bits exceeds
// the number of non-set bits,
// then add set bits value to ans
if (S > NS)
ans += pow(2,i);
getBit <<= 1;
}
return ans;
}
// Perform Inorder Traversal
// on the Binary Tree
void diagonalOrder(TreeNode *root,int d,map<int,vector<int> > &mp){
if (!root)
return;
// Store all nodes of the same
// line together as a vector
mp[d].push_back(root->val);
// Increase the vertical
// distance of left child
diagonalOrder(root->left, d + 1, mp);
// Vertical distance remains
// same for right child
diagonalOrder(root->right, d, mp);
}
// Function to compress a given
// Binary Tree into an integer
int findInteger(TreeNode *root){
// Declare a map
map<int,vector<int> > mp;
diagonalOrder(root, 0, mp);
//Store all the compressed values of
//diagonal elements in an array
vector<int> arr;
for (auto i:mp)
arr.push_back(findCompressValue(i.second));
// Compress the array into an integer
return findCompressValue(arr);
}
// Driver Code
// Given Input
int main()
{
TreeNode *root = new TreeNode(6);
root->left = new TreeNode(5);
root->right = new TreeNode(3);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(4);
// Function Call
cout << findInteger(root);
return 0;
}
// This code is contributed by mohit kumar 29.
Python3
# Python program for the above approach
class TreeNode:
def __init__(self, val ='',
left = None,
right = None):
self.val = val
self.left = left
self.right = right
# Function to compress the elements
# in an array into an integer
def findCompressValue(arr):
ans = 0
getBit = 1
# Check for each bit position
for i in range(32):
S = 0
NS = 0
for j in arr:
# Update the count of
# set and non-set bits
if getBit & j:
S += 1
else:
NS += 1
# If number of set bits exceeds
# the number of non-set bits,
# then add set bits value to ans
if S > NS:
ans += 2**i
getBit <<= 1
return ans
# Function to compress a given
# Binary Tree into an integer
def findInteger(root):
# Declare a map
mp = {}
# Perform Inorder Traversal
# on the Binary Tree
def diagonalOrder(root, d, mp):
if not root:
return
# Store all nodes of the same
# line together as a vector
try:
mp[d].append(root.val)
except KeyError:
mp[d] = [root.val]
# Increase the vertical
# distance of left child
diagonalOrder(root.left, d + 1, mp)
# Vertical distance remains
# same for right child
diagonalOrder(root.right, d, mp)
diagonalOrder(root, 0, mp)
# Store all the compressed values of
# diagonal elements in an array
arr = []
for i in mp:
arr.append(findCompressValue(mp[i]))
# Compress the array into an integer
return findCompressValue(arr)
# Driver Code
# Given Input
root = TreeNode(6)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
root.right.left = TreeNode(3)
root.right.right = TreeNode(4)
# Function Call
print(findInteger(root))
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA