Dado un árbol binario , la tarea es encontrar el número de caminos diagonales a la hoja de un árbol binario tal que los valores de todos los Nodes en la misma diagonal sean iguales.
Ejemplos:
Aporte:
5 / \ 6 5 \ \ 6 5Salida: 2
Explicación:
Diagonal 6 – 6 y 5 – 5 contiene el mismo valor.
Por lo tanto, la salida requerida es 2.Aporte:
5 / \ 6 5 \ \ 5 5Salida: 1
Enfoque: La idea principal es recorrer el árbol en diagonal usando un Mapa . Siga los pasos a continuación para resolver este problema:
- Atraviese el árbol binario dado en orden diagonal y almacene el Node inicial de cada diagonal como la clave y para cada clave , almacene todos los valores en esa diagonal en un Hashset .
- Después del recorrido, encuentre el número de claves que tienen un tamaño del conjunto igual a 1 e imprímalo como la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val = 0;
TreeNode *left, *right;
TreeNode(int x)
{
val = x;
left = NULL;
right = NULL;
}
};
// Function to perform diagonal
// traversal on the given binary tree
void fillMap(TreeNode *root, int left,
map<int, set<int>> &diag)
{
// If tree is empty
if (!root)
return;
// If current diagonal is not visited
if (diag[left].size() == 0)
{
// Update diag[left]
diag[left].insert(root->val);
}
// Otherwise, map current node
// with its diagonal
else
diag[left].insert(root->val);
// Recursively, traverse left subtree
fillMap(root->left, left + 1, diag);
// Recursively, traverse right subtree
fillMap(root->right, left, diag);
}
// Function to count diagonal
// paths having same-valued nodes
int sameDiag(TreeNode *root)
{
// Maps the values of all
// nodes with its diagonal
map<int, set<int>> diag;
// Stores indexing of diagonal
int left = 0;
// Function call to perform
// diagonal traversal
fillMap(root, left, diag);
// Stores count of diagonals such
// that all the nodes on the same
// diagonal are equal
int count = 0;
// Traverse each diagonal
for(auto d : diag)
{
// If all nodes on the current
// diagonal are equal
if (diag[d.first].size() == 1)
// Update count
count += 1;
}
return count;
}
// Driver Code
int main()
{
// Given tree
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(6);
root->right = new TreeNode(5);
root->left->right = new TreeNode(6);
root->right->right = new TreeNode(5);
// Function call
cout << sameDiag(root);
}
// This code is contributed by mohit kumar 29
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG
{
// Structure of a Node
static class TreeNode
{
int val;
TreeNode left, right;
TreeNode(int key)
{
val = key;
left = null;
right = null;
}
};
// Function to perform diagonal
// traversal on the given binary tree
static void fillMap(TreeNode root, int left,
Map<Integer,Set<Integer>> diag)
{
// If tree is empty
if (root == null)
return;
// If current diagonal is not visited
if (diag.get(left) == null)
{
// Update diag[left]
diag.put(left, new HashSet<Integer>());
diag.get(left).add(root.val);
}
// Otherwise, map current node
// with its diagonal
else
diag.get(left).add(root.val);
// Recursively, traverse left subtree
fillMap(root.left, left + 1, diag);
// Recursively, traverse right subtree
fillMap(root.right, left, diag);
}
// Function to count diagonal
// paths having same-valued nodes
static int sameDiag(TreeNode root)
{
// Maps the values of all
// nodes with its diagonal
Map<Integer, Set<Integer>> diag = new HashMap<>();
// Stores indexing of diagonal
int left = 0;
// Function call to perform
// diagonal traversal
fillMap(root, left, diag);
// Stores count of diagonals such
// that all the nodes on the same
// diagonal are equal
int count = 0;
// Traverse each diagonal
for(Map.Entry<Integer,Set<Integer>> d:diag.entrySet())
{
// If all nodes on the current
// diagonal are equal
if (d.getValue().size() == 1)
// Update count
count += 1;
}
return count;
}
// Driver function
public static void main (String[] args)
{
TreeNode root = new TreeNode(5);
root.left = new TreeNode(6);
root.right = new TreeNode(5);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(5);
System.out.println(sameDiag(root));
}
}
// This code is contributed by offbeat
Python3
# Python3 program of the above approach
# Structure of a Node
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
# Function to count diagonal
# paths having same-valued nodes
def sameDiag(root):
# Maps the values of all
# nodes with its diagonal
diag = {}
# Stores indexing of diagonal
left = 0
# Function to perform diagonal
# traversal on the given binary tree
def fillMap(root, left):
# If tree is empty
if not root:
return
# If current diagonal is not visited
if left not in diag:
# Update diag[left]
diag[left] = set([root.val])
# Otherwise, map current node
# with its diagonal
else:
diag[left].add(root.val)
# Recursively, traverse left subtree
fillMap(root.left, left + 1)
# Recursively, traverse right subtree
fillMap(root.right, left)
# Function call to perform
# diagonal traversal
fillMap(root, left)
# Stores count of diagonals such
# that all the nodes on the same
# diagonal are equal
count = 0
# Traverse each diagonal
for d in diag:
# If all nodes on the current
# diagonal are equal
if len(list(diag[d])) == 1:
# Update count
count += 1
return count
# Driver Code
if __name__ == '__main__':
# Given tree
root = TreeNode(5)
root.left = TreeNode(6)
root.right = TreeNode(5)
root.left.right = TreeNode(6)
root.right.right = TreeNode(5)
# Function call
print(sameDiag(root))
Javascript
<script>
// JavaScript program for above approach
// Structure of a Node
class TreeNode
{
constructor(key)
{
this.val=key;
this.left=this.right=null;
}
}
// Function to perform diagonal
// traversal on the given binary tree
function fillMap(root,left,diag)
{
// If tree is empty
if (root == null)
return;
// If current diagonal is not visited
if (diag.get(left) == null)
{
// Update diag[left]
diag.set(left, new Set());
diag.get(left).add(root.val);
}
// Otherwise, map current node
// with its diagonal
else
diag.get(left).add(root.val);
// Recursively, traverse left subtree
fillMap(root.left, left + 1, diag);
// Recursively, traverse right subtree
fillMap(root.right, left, diag);
}
// Function to count diagonal
// paths having same-valued nodes
function sameDiag(root)
{
// Maps the values of all
// nodes with its diagonal
let diag = new Map();
// Stores indexing of diagonal
let left = 0;
// Function call to perform
// diagonal traversal
fillMap(root, left, diag);
// Stores count of diagonals such
// that all the nodes on the same
// diagonal are equal
let count = 0;
// Traverse each diagonal
for(let [key, value] of diag.entries())
{
// If all nodes on the current
// diagonal are equal
if (value.size == 1)
// Update count
count += 1;
}
return count;
}
// Driver function
let root = new TreeNode(5);
root.left = new TreeNode(6);
root.right = new TreeNode(5);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(5);
document.write(sameDiag(root));
// This code is contributed by patel2127
</script>
C#
using System;
using System.Collections.Generic;
public class TreeNode
{
public int val;
public TreeNode left, right;
public TreeNode(int key)
{
val = key;
left = null;
right = null;
}
}
public class GFG{
// Function to perform diagonal
// traversal on the given binary tree
static void fillMap(TreeNode root, int left,
Dictionary<int,HashSet<int>> diag)
{
// If tree is empty
if (root == null)
return;
// If current diagonal is not visited
if (!diag.ContainsKey(left))
{
// Update diag[left]
diag.Add(left, new HashSet<int>());
diag[left].Add(root.val);
}
// Otherwise, map current node
// with its diagonal
else
diag[left].Add(root.val);
// Recursively, traverse left subtree
fillMap(root.left, left + 1, diag);
// Recursively, traverse right subtree
fillMap(root.right, left, diag);
}
// Function to count diagonal
// paths having same-valued nodes
static int sameDiag(TreeNode root)
{
// Maps the values of all
// nodes with its diagonal
Dictionary<int,HashSet<int>> diag = new Dictionary<int,HashSet<int>>();
// Stores indexing of diagonal
int left = 0;
// Function call to perform
// diagonal traversal
fillMap(root, left, diag);
// Stores count of diagonals such
// that all the nodes on the same
// diagonal are equal
int count = 0;
// Traverse each diagonal
foreach(KeyValuePair<int,HashSet<int>> d in diag)
{
// If all nodes on the current
// diagonal are equal
if (d.Value.Count == 1)
// Update count
count += 1;
}
return count;
}
// Driver function
static public void Main (){
TreeNode root = new TreeNode(5);
root.left = new TreeNode(6);
root.right = new TreeNode(5);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(5);
Console.WriteLine(sameDiag(root));
}
}
Producción:
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