Encuentre el nivel en un árbol binario que tiene el número máximo de Nodes. La raíz está en el nivel 0.
Ejemplos:
C++
// C++ implementation to find the level
// having maximum number of Nodes
#include <bits/stdc++.h>
using namespace std;
/* A binary tree Node has data, pointer
to left child and a pointer to right
child */
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
/* Helper function 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 = NULL;
node->right = NULL;
return(node);
}
// function to find the level
// having maximum number of Nodes
int maxNodeLevel(Node *root)
{
if (root == NULL)
return -1;
queue<Node *> q;
q.push(root);
// Current level
int level = 0;
// Maximum Nodes at same level
int max = INT_MIN;
// Level having maximum Nodes
int level_no = 0;
while (1)
{
// Count Nodes in a level
int NodeCount = q.size();
if (NodeCount == 0)
break;
// If it is maximum till now
// Update level_no to current level
if (NodeCount > max)
{
max = NodeCount;
level_no = level;
}
// Pop complete current level
while (NodeCount > 0)
{
Node *Node = q.front();
q.pop();
if (Node->left != NULL)
q.push(Node->left);
if (Node->right != NULL)
q.push(Node->right);
NodeCount--;
}
// Increment for next level
level++;
}
return level_no;
}
// Driver program to test above
int main()
{
// binary tree formation
struct Node *root = newNode(2); /* 2 */
root->left = newNode(1); /* / \ */
root->right = newNode(3); /* 1 3 */
root->left->left = newNode(4); /* / \ \ */
root->left->right = newNode(6); /* 4 6 8 */
root->right->right = newNode(8); /* / */
root->left->right->left = newNode(5);/* 5 */
printf("Level having maximum number of Nodes : %d",
maxNodeLevel(root));
return 0;
}
Java
// Java implementation to find the level
// having maximum number of Nodes
import java.util.*;
class GfG {
/* A binary tree Node has data, pointer
to left child and a pointer to right
child */
static class Node
{
int data;
Node left;
Node right;
}
/* Helper function 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 = null;
node.right = null;
return(node);
}
// function to find the level
// having maximum number of Nodes
static int maxNodeLevel(Node root)
{
if (root == null)
return -1;
Queue<Node> q = new LinkedList<Node> ();
q.add(root);
// Current level
int level = 0;
// Maximum Nodes at same level
int max = Integer.MIN_VALUE;
// Level having maximum Nodes
int level_no = 0;
while (true)
{
// Count Nodes in a level
int NodeCount = q.size();
if (NodeCount == 0)
break;
// If it is maximum till now
// Update level_no to current level
if (NodeCount > max)
{
max = NodeCount;
level_no = level;
}
// Pop complete current level
while (NodeCount > 0)
{
Node Node = q.peek();
q.remove();
if (Node.left != null)
q.add(Node.left);
if (Node.right != null)
q.add(Node.right);
NodeCount--;
}
// Increment for next level
level++;
}
return level_no;
}
// Driver program to test above
public static void main(String[] args)
{
// binary tree formation
Node root = newNode(2); /* 2 */
root.left = newNode(1); /* / \ */
root.right = newNode(3); /* 1 3 */
root.left.left = newNode(4); /* / \ \ */
root.left.right = newNode(6); /* 4 6 8 */
root.right.right = newNode(8); /* / */
root.left.right.left = newNode(5);/* 5 */
System.out.println("Level having maximum number of Nodes : " + maxNodeLevel(root));
}
}
Python3
# Python3 implementation to find the
# level having Maximum number of Nodes
# Importing Queue
from queue import Queue
# Helper class that allocates a new
# node with the given data and None
# left and right pointers.
class newNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# function to find the level
# having Maximum number of Nodes
def maxNodeLevel(root):
if (root == None):
return -1
q = Queue()
q.put(root)
# Current level
level = 0
# Maximum Nodes at same level
Max = -999999999999
# Level having Maximum Nodes
level_no = 0
while (1):
# Count Nodes in a level
NodeCount = q.qsize()
if (NodeCount == 0):
break
# If it is Maximum till now
# Update level_no to current level
if (NodeCount > Max):
Max = NodeCount
level_no = level
# Pop complete current level
while (NodeCount > 0):
Node = q.queue[0]
q.get()
if (Node.left != None):
q.put(Node.left)
if (Node.right != None):
q.put(Node.right)
NodeCount -= 1
# Increment for next level
level += 1
return level_no
# Driver Code
if __name__ == '__main__':
# binary tree formation
root = newNode(2) # 2
root.left = newNode(1) # / \
root.right = newNode(3) # 1 3
root.left.left = newNode(4) # / \ \
root.left.right = newNode(6) # 4 6 8
root.right.right = newNode(8) # /
root.left.right.left = newNode(5)# 5
print("Level having Maximum number of Nodes : ",
maxNodeLevel(root))
# This code is contributed by Pranchalk
C#
using System;
using System.Collections.Generic;
// C# implementation to find the level
// having maximum number of Nodes
public class GfG
{
/* A binary tree Node has data, pointer
to left child and a pointer to right
child */
public class Node
{
public int data;
public Node left;
public Node right;
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
public static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// function to find the level
// having maximum number of Nodes
public static int maxNodeLevel(Node root)
{
if (root == null)
{
return -1;
}
LinkedList<Node> q = new LinkedList<Node> ();
q.AddLast(root);
// Current level
int level = 0;
// Maximum Nodes at same level
int max = int.MinValue;
// Level having maximum Nodes
int level_no = 0;
while (true)
{
// Count Nodes in a level
int NodeCount = q.Count;
if (NodeCount == 0)
{
break;
}
// If it is maximum till now
// Update level_no to current level
if (NodeCount > max)
{
max = NodeCount;
level_no = level;
}
// Pop complete current level
while (NodeCount > 0)
{
Node Node = q.First.Value;
q.RemoveFirst();
if (Node.left != null)
{
q.AddLast(Node.left);
}
if (Node.right != null)
{
q.AddLast(Node.right);
}
NodeCount--;
}
// Increment for next level
level++;
}
return level_no;
}
// Driver program to test above
public static void Main(string[] args)
{
// binary tree formation
Node root = newNode(2); // 2
root.left = newNode(1); // / \
root.right = newNode(3); // 1 3
root.left.left = newNode(4); // / \ \
root.left.right = newNode(6); // 4 6 8
root.right.right = newNode(8); // /
root.left.right.left = newNode(5); // 5
Console.WriteLine("Level having maximum number of Nodes : " + maxNodeLevel(root));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript implementation to find the level
// having maximum number of Nodes
/* A binary tree Node has data, pointer
to left child and a pointer to right
child */
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
}
/* Helper function 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 = null;
node.right = null;
return (node);
}
// function to find the level
// having maximum number of Nodes
function maxNodeLevel(root)
{
if (root == null)
{
return -1;
}
var q = [];
q.push(root);
// Current level
var level = 0;
// Maximum Nodes at same level
var max = -1000000000;
// Level having maximum Nodes
var level_no = 0;
while (true)
{
// length Nodes in a level
var NodeCount = q.length;
if (NodeCount == 0)
{
break;
}
// If it is maximum till now
// Update level_no to current level
if (NodeCount > max)
{
max = NodeCount;
level_no = level;
}
// Pop complete current level
while (NodeCount > 0)
{
var Node = q[0];
q.shift();
if (Node.left != null)
{
q.push(Node.left);
}
if (Node.right != null)
{
q.push(Node.right);
}
NodeCount--;
}
// Increment for next level
level++;
}
return level_no;
}
// Driver program to test above
// binary tree formation
var root = newNode(2); // 2
root.left = newNode(1); // / \
root.right = newNode(3); // 1 3
root.left.left = newNode(4); // / \ \
root.left.right = newNode(6); // 4 6 8
root.right.right = newNode(8); // /
root.left.right.left = newNode(5); // 5
document.write("Level having maximum number of Nodes : " + maxNodeLevel(root));
// This code is contributed by famously.
</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