Comprimir un árbol binario en un entero en diagonal

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) ₂ , (110) ₂ , (011) ₂ y (100) ₂ 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) ₂ = 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:

#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.

# 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)