Dado un árbol binario, imprima el número de caminos de raíz a hoja que tienen longitudes iguales.
Ejemplos:
C++
// C++ program to count root to leaf paths of different
// lengths.
#include<bits/stdc++.h>
using namespace std;
/* A binary tree node */
struct Node
{
int data;
struct Node* left, *right;
};
/* utility that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newnode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Function to store counts of different root to leaf
// path lengths in hash map m.
void pathCountUtil(Node *node, unordered_map<int, int> &m,
int path_len)
{
// Base condition
if (node == NULL)
return;
// If leaf node reached, increment count of path
// length of this root to leaf path.
if (node->left == NULL && node->right == NULL)
{
m[path_len]++;
return;
}
// Recursively call for left and right subtrees with
// path lengths more than 1.
pathCountUtil(node->left, m, path_len+1);
pathCountUtil(node->right, m, path_len+1);
}
// A wrapper over pathCountUtil()
void pathCounts(Node *root)
{
// create an empty hash table
unordered_map<int, int> m;
// Recursively check in left and right subtrees.
pathCountUtil(root, m, 1);
// Print all path lengths and their counts.
for (auto itr=m.begin(); itr != m.end(); itr++)
cout << itr->second << " paths have length "
<< itr->first << endl;
}
// Driver program to run the case
int main()
{
struct Node *root = newnode(8);
root->left = newnode(5);
root->right = newnode(4);
root->left->left = newnode(9);
root->left->right = newnode(7);
root->right->right = newnode(11);
root->right->right->left = newnode(3);
pathCounts(root);
return 0;
}
Java
// Java program to count root to leaf
// paths of different lengths.
import java.util.HashMap;
import java.util.Map;
class GFG{
// A binary tree node
static class Node
{
int data;
Node left, right;
};
// Utility that allocates a new node
// with the given data and null left
// and right pointers.
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Function to store counts of different
// root to leaf path lengths in hash map m.
static void pathCountUtil(Node node,
HashMap<Integer, Integer> m, int path_len)
{
// Base condition
if (node == null)
return;
// If leaf node reached, increment count
// of path length of this root to leaf path.
if (node.left == null && node.right == null)
{
if (!m.containsKey(path_len))
m.put(path_len, 0);
m.put(path_len, m.get(path_len) + 1);
return;
}
// Recursively call for left and right
// subtrees with path lengths more than 1.
pathCountUtil(node.left, m, path_len + 1);
pathCountUtil(node.right, m, path_len + 1);
}
// A wrapper over pathCountUtil()
static void pathCounts(Node root)
{
// Create an empty hash table
HashMap<Integer, Integer> m = new HashMap<>();
// Recursively check in left and right subtrees.
pathCountUtil(root, m, 1);
// Print all path lengths and their counts.
for(Map.Entry<Integer,
Integer> entry : m.entrySet())
{
System.out.printf("%d paths have length %d\n",
entry.getValue(),
entry.getKey());
}
}
// Driver code
public static void main(String[] args)
{
Node root = newnode(8);
root.left = newnode(5);
root.right = newnode(4);
root.left.left = newnode(9);
root.left.right = newnode(7);
root.right.right = newnode(11);
root.right.right.left = newnode(3);
pathCounts(root);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to count root to leaf
# paths of different lengths.
# Binary Tree Node
""" utility that allocates a newNode
with the given key """
class newnode:
# Construct to create a newNode
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Function to store counts of different
# root to leaf path lengths in hash map m.
def pathCountUtil(node, m,path_len) :
# Base condition
if (node == None) :
return
# If leaf node reached, increment count of
# path length of this root to leaf path.
if (node.left == None and node.right == None):
if path_len[0] not in m:
m[path_len[0]] = 0
m[path_len[0]] += 1
return
# Recursively call for left and right
# subtrees with path lengths more than 1.
pathCountUtil(node.left, m, [path_len[0] + 1])
pathCountUtil(node.right, m, [path_len[0] + 1])
# A wrapper over pathCountUtil()
def pathCounts(root) :
# create an empty hash table
m = {}
path_len = [1]
# Recursively check in left and right subtrees.
pathCountUtil(root, m, path_len)
# Print all path lengths and their counts.
for itr in sorted(m, reverse = True):
print(m[itr], " paths have length ", itr)
# Driver Code
if __name__ == '__main__':
root = newnode(8)
root.left = newnode(5)
root.right = newnode(4)
root.left.left = newnode(9)
root.left.right = newnode(7)
root.right.right = newnode(11)
root.right.right.left = newnode(3)
pathCounts(root)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to count root to leaf
// paths of different lengths.
using System;
using System.Collections.Generic;
class GFG
{
// A binary tree node
public
class Node
{
public
int data;
public
Node left,
right;
};
// Utility that allocates a new node
// with the given data and null left
// and right pointers.
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Function to store counts of different
// root to leaf path lengths in hash map m.
static void pathCountUtil(Node node,
Dictionary<int, int> m,
int path_len)
{
// Base condition
if (node == null)
return;
// If leaf node reached, increment count
// of path length of this root to leaf path.
if (node.left == null && node.right == null)
{
if (!m.ContainsKey(path_len))
m.Add(path_len, 1);
else
m[path_len] = m[path_len] + 1;
return;
}
// Recursively call for left and right
// subtrees with path lengths more than 1.
pathCountUtil(node.right, m, path_len + 1);
pathCountUtil(node.left, m, path_len + 1);
}
// A wrapper over pathCountUtil()
static void pathCounts(Node root)
{
// Create an empty hash table
Dictionary<int, int> m = new Dictionary<int, int>();
// Recursively check in left and right subtrees.
pathCountUtil(root, m, 1);
// Print all path lengths and their counts.
foreach(KeyValuePair<int, int> entry in m)
{
Console.WriteLine(entry.Value
+ " paths have length "
+ entry.Key);
}
}
// Driver code
public static void Main(String[] args)
{
Node root = newnode(8);
root.left = newnode(5);
root.right = newnode(4);
root.left.left = newnode(9);
root.left.right = newnode(7);
root.right.right = newnode(11);
root.right.right.left = newnode(3);
pathCounts(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to count root to leaf
// paths of different lengths.
// A binary tree node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Utility that allocates a new node
// with the given data and null left
// and right pointers.
function newnode(data)
{
var node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Function to store counts of different
// root to leaf path lengths in hash map m.
function pathCountUtil(node, m, path_len)
{
// Base condition
if (node == null)
return;
// If leaf node reached, increment count
// of path length of this root to leaf path.
if (node.left == null && node.right == null)
{
if (!m.has(path_len))
m.set(path_len, 1);
else
m.set(path_len, m.get(path_len) + 1);
return;
}
// Recursively call for left and right
// subtrees with path lengths more than 1.
pathCountUtil(node.right, m, path_len + 1);
pathCountUtil(node.left, m, path_len + 1);
}
// A wrapper over pathCountUtil()
function pathCounts(root)
{
// Create an empty hash table
var m = new Map();
// Recursively check in left and right subtrees.
pathCountUtil(root, m, 1);
// Print all path lengths and their counts.
m.forEach((value, key) => {
document.write(value + " paths have length " +
key + "<br>");
});
}
// Driver code
var root = newnode(8);
root.left = newnode(5);
root.right = newnode(4);
root.left.left = newnode(9);
root.left.right = newnode(7);
root.right.right = newnode(11);
root.right.right.left = newnode(3);
pathCounts(root);
// This code is contributed by itsok
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA