Dado un árbol binario , la tarea es comprimir todos los Nodes en la misma línea vertical en un solo Node de tal manera que si el conteo de bits establecidos de todos los Nodes en una línea vertical en cualquier posición es mayor que el conteo de bits claros en esa posición, entonces se establece el bit del Node único en esa posición.
Ejemplos:
Aporte:
1 \ 2 / 1 \ 3Salida: 1 2
Explicación:
1 y 1 están a la misma distancia vertical, cuenta del bit establecido en la posición 0 = 2 y cuenta del bit borrado = 0. Por lo tanto, se establece el bit 0 del Node resultante.
2 y 3 están a la misma distancia vertical, el recuento de bits establecidos en la pos. 0 = 1 y el recuento de bits borrados = 1. Por lo tanto, se establece el bit 0 del Node resultante no se establece.
2 y 3 están a la misma distancia vertical, el recuento de bits establecidos en la primera posición = 2 y el recuento de bits borrados = 0. Por lo tanto, se establece el primer bit del Node resultante.
Aporte:
1 / \ 3 2 / \ / \ 1 4 1 2Salida: 1 3 5 2 2
Enfoque: La idea es atravesar el árbol y mantener un registro de la distancia horizontal desde el Node raíz para cada Node visitado. A continuación se muestran los pasos:
- Se puede utilizar un mapa para almacenar la distancia horizontal desde el Node raíz como clave y los valores de los Nodes como valores .
- Después de almacenar los valores en el mapa, verifique el número de bits establecidos y no establecidos para cada posición y calcule los valores en consecuencia.
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 a node of the tree class Node { public: int val; Node *left, *right; Node(int val) { this->val = val; left = right = NULL; } }; // Function to compress all the nodes on the same vertical // line void evalComp(vector<int>& arr) { // Stores node by compressing all nodes on the current // vertical line int ans = 0; // Check if i-th bit of current bit set or not int getBit = 1; // Iterate over the range [0, 31] for (int i = 0; i < 32; i++) { // Stores count of set bits at i-th positions int S = 0; // Stores count of clear bits at i-th positions int NS = 0; // Traverse the array for (auto j : arr) { // If i-th bit of current element is set if (getBit & j) S++; // Update S else NS++; // Update NS } // If count of set bits at i-th position is greater // than count of clear bits if (S > NS) // Update ans ans += pow(2, i); // Update getBit getBit <<= 1; } cout << ans << " "; } // Function to traverse the tree and map all the nodes of // same vertical line to vertical distance void Trav(Node* root, int hd, map<int, vector<int> >& mp) { if (!root) return; // Storing the values in the map mp[hd].push_back(root->val); // Recursive calls on left and right subtree Trav(root->left, hd - 1, mp); Trav(root->right, hd + 1, mp); } // Function to compress all the nodes on the same vertical // line with a single node that satisfies the condition void compressTree(Node* root) { // Map all the nodes on the same vertical line map<int, vector<int> > mp; Trav(root, 0, mp); // Getting the range of horizontal distances int lower, upper; for (auto i : mp) { lower = min(lower, i.first); upper = max(upper, i.first); } for (int i = lower; i <= upper; i++) evalComp(mp[i]); } // Driver Code int main() { Node* root = new Node(5); root->left = new Node(3); root->right = new Node(2); root->left->left = new Node(1); root->left->right = new Node(4); root->right->left = new Node(1); root->right->right = new Node(2); // Function Call compressTree(root); return 0; } // This code is contributed by Tapesh(tapeshdua420)
Java
// Java program for the above approach import java.util.*; class GFG { // Structure of a node of the tree static class Node { int val; Node left, right; Node(int val) { this.val = val; left = right = null; } } // Driver Code public static void main(String[] args) { Node root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.left.left = new Node(1); root.left.right = new Node(4); root.right.left = new Node(1); root.right.right = new Node(2); compressTree(root); } // Function to compress all the nodes on the same // vertical line public static void evalComp(ArrayList<Integer> arr) { // Stores node by compressing all nodes on the // currentvertical line int ans = 0; // Check if i-th bit of current bit set or not int getBit = 1; // Iterate over the range [0, 31] for (int i = 0; i < 32; i++) { // Stores count of set bits at i-th positions int S = 0; // Stores count of clear bits at i-th positions int NS = 0; // Traverse the array for (int j : arr) { // If i-th bit of current element is set if ((getBit & j) != 0) S++; // Update S else NS++; // Update NS } // If count of set bits at i-th position is // greater // than count of clear bits if (S > NS) // Update ans ans += Math.pow(2, i); // Update getBit getBit <<= 1; } System.out.print(ans + " "); } // Function to traverse the tree and map all the nodes // of same vertical line to vertical distance public static void Trav(Node root, int hd, HashMap<Integer, ArrayList<Integer> > mp) { if (root == null) return; // Storing the values in the map mp.putIfAbsent(hd, new ArrayList<>()); mp.get(hd).add(root.val); // Recursive calls on left and right subtree Trav(root.left, hd - 1, mp); Trav(root.right, hd + 1, mp); } // Function to compress all the nodes on the same // vertical // line with a single node that satisfies the condition public static void compressTree(Node root) { // Map all the nodes on the same vertical line HashMap<Integer, ArrayList<Integer> > mp = new HashMap<>(); Trav(root, 0, mp); // Getting the range of horizontal distances int lower = Integer.MAX_VALUE, upper = Integer.MIN_VALUE; for (Map.Entry<Integer, ArrayList<Integer> > i : mp.entrySet()) { lower = Math.min(lower, i.getKey()); upper = Math.max(upper, i.getKey()); } for (int i = lower; i <= upper; i++) evalComp(mp.get(i)); } } // This code is contributed by Tapesh(tapeshdua420)
Python3
# Python3 program for the above approach # Structure of a node # of th tree class TreeNode: def __init__(self, val ='', left = None, right = None): self.val = val self.left = left self.right = right # Function to compress all the nodes # on the same vertical line def evalComp(arr): # Stores node by compressing all # nodes on the current vertical line ans = 0 # Check if i-th bit of current bit # set or not getBit = 1 # Iterate over the range [0, 31] for i in range(32): # Stores count of set bits # at i-th positions S = 0 # Stores count of clear bits # at i-th positions NS = 0 # Traverse the array for j in arr: # If i-th bit of current element # is set if getBit & j: # Update S S += 1 else: # Update NS NS += 1 # If count of set bits at i-th position # is greater than count of clear bits if S > NS: # Update ans ans += 2**i # Update getBit getBit <<= 1 print(ans, end = " ") # Function to compress all the nodes on # the same vertical line with a single node # that satisfies the condition def compressTree(root): # Map all the nodes on the same vertical line mp = {} # Function to traverse the tree and map # all the nodes of same vertical line # to vertical distance def Trav(root, hd): if not root: return # Storing the values in the map if hd not in mp: mp[hd] = [root.val] else: mp[hd].append(root.val) # Recursive calls on left and right subtree Trav(root.left, hd-1) Trav(root.right, hd + 1) Trav(root, 0) # Getting the range of # horizontal distances lower = min(mp.keys()) upper = max(mp.keys()) for i in range(lower, upper + 1): evalComp(mp[i]) # Driver Code if __name__ == '__main__': root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(2) root.left.left = TreeNode(1) root.left.right = TreeNode(4) root.right.left = TreeNode(1) root.right.right = TreeNode(2) # Function Call compressTree(root)
C#
// C# program for the above approach using System; using System.Collections.Generic; // Structure of a node of the tree class Node { public int val; public Node left; public Node right; public Node(int data) { val = data; left = right = null; } } class Program { // Driver Code static void Main(string[] args) { Node root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.left.left = new Node(1); root.left.right = new Node(4); root.right.left = new Node(1); root.right.right = new Node(2); compressTree(root); } // Function to compress all the nodes on the same // vertical line public static void evalComp(List<int> arr) { // Stores node by compressing all nodes on the // currentvertical line int ans = 0; // Check if i-th bit of current bit set or not int getBit = 1; // Iterate over the range [0, 31] for (int i = 0; i < 32; i++) { // Stores count of set bits at i-th positions int S = 0; // Stores count of clear bits at i-th positions int NS = 0; // Traverse the array foreach(int j in arr) { // If i-th bit of current element is set if ((getBit & j) != 0) S++; // Update S else NS++; // Update NS } // If count of set bits at i-th position is // greater // than count of clear bits if (S > NS) // Update ans ans += (int)Math.Pow(2, i); // Update getBit getBit <<= 1; } Console.Write(ans + " "); } // Function to traverse the tree and map all the nodes // of same vertical line to vertical distance public static void Trav(Node root, int hd, Dictionary<int, List<int> > mp) { if (root == null) return; // Storing the values in the map if (mp.ContainsKey(hd) == false) mp[hd] = new List<int>(); mp[hd].Add(root.val); // Recursive calls on left and right subtree Trav(root.left, hd - 1, mp); Trav(root.right, hd + 1, mp); } // Function to compress all the nodes on the same // vertical // line with a single node that satisfies the condition public static void compressTree(Node root) { // Map all the nodes on the same vertical line Dictionary<int, List<int> > mp = new Dictionary<int, List<int> >(); Trav(root, 0, mp); // Getting the range of horizontal distances int lower = Int32.MaxValue, upper = Int32.MinValue; foreach(KeyValuePair<int, List<int> > i in mp) { lower = Math.Min(lower, i.Key); upper = Math.Max(upper, i.Key); } for (int i = lower; i <= upper; i++) evalComp(mp[i]); } } // This code is contributed by Tapesh(tapeshdua420)
Javascript
<script> // Javascript program for the above approach // Structure of a node // of th tree class TreeNode { constructor(val = "", left = null, right = null) { this.val = val; this.left = left; this.right = right; } } // Function to compress all the nodes // on the same vertical line function evalComp(arr) { // Stores node by compressing all // nodes on the current vertical line let ans = 0; // Check if i-th bit of current bit // set or not let getBit = 1; // Iterate over the range [0, 31] for (let i = 0; i < 32; i++) { // Stores count of set bits // at i-th positions let S = 0; // Stores count of clear bits // at i-th positions let NS = 0; // Traverse the array for (j of arr) { // If i-th bit of current element // is set if (getBit & j) // Update S S += 1; // Update NS else NS += 1; } // If count of set bits at i-th position // is greater than count of clear bits if (S > NS) // Update ans ans += 2 ** i; // Update getBit getBit <<= 1; } document.write(ans + " "); } // Function to compress all the nodes on // the same vertical line with a single node // that satisfies the condition function compressTree(root) { // Map all the nodes on the same vertical line let mp = new Map(); // Function to traverse the tree and map // all the nodes of same vertical line // to vertical distance function Trav(root, hd) { if (!root) return; // Storing the values in the map if (!mp.has(hd)) mp.set(hd, [root.val]); else { let temp = mp.get(hd); temp.push(root.val); mp.set(hd, temp); } // Recursive calls on left and right subtree Trav(root.left, hd - 1); Trav(root.right, hd + 1); } Trav(root, 0); // Getting the range of // horizontal distances let lower = [...mp.keys()].sort((a, b) => a - b)[0]; let upper = [...mp.keys()].sort((a, b) => b - a)[0]; for (let i = lower; i <= upper; i++) evalComp(mp.get(i)); } // Driver Code let root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(2); root.left.left = new TreeNode(1); root.left.right = new TreeNode(4); root.right.left = new TreeNode(1); root.right.right = new TreeNode(2); // Function Call compressTree(root); // This code is contributed by _saurabh_jaiswal. </script>
1 3 5 2 2
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