Dado un árbol binario, encuentre el valor más grande en cada nivel.
Ejemplos:
Input :
1
/ \
2 3
Output : 1 3
Input :
4
/ \
9 2
/ \ \
3 5 7
Output : 4 9 7
C++
// C++ program to find largest
// value on each level of binary tree.
#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 val;
struct Node *left, *right;
};
/* Recursive function to find
the largest value on each level */
void helper(vector<int>& res, Node* root, int d)
{
if (!root)
return;
// Expand list size
if (d == res.size())
res.push_back(root->val);
else
// to ensure largest value
// on level is being stored
res[d] = max(res[d], root->val);
// Recursively traverse left and
// right subtrees in order to find
// out the largest value on each level
helper(res, root->left, d + 1);
helper(res, root->right, d + 1);
}
// function to find largest values
vector<int> largestValues(Node* root)
{
vector<int> res;
helper(res, root, 0);
return res;
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver code
int main()
{
/* Let us construct a Binary Tree
4
/ \
9 2
/ \ \
3 5 7 */
Node* root = NULL;
root = newNode(4);
root->left = newNode(9);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->right = newNode(7);
vector<int> res = largestValues(root);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
return 0;
}
Java
// Java program to find largest
// value on each level of binary tree.
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 val;
Node left, right;
};
/* Recursive function to find
the largest value on each level */
static void helper(Vector<Integer> res, Node root, int d)
{
if (root == null)
return;
// Expand list size
if (d == res.size())
res.add(root.val);
else
// to ensure largest value
// on level is being stored
res.set(d, Math.max(res.get(d), root.val));
// Recursively traverse left and
// right subtrees in order to find
// out the largest value on each level
helper(res, root.left, d + 1);
helper(res, root.right, d + 1);
}
// function to find largest values
static Vector<Integer> largestValues(Node root)
{
Vector<Integer> res = new Vector<>();
helper(res, root, 0);
return res;
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void main(String[] args)
{
/* Let us construct a Binary Tree
4
/ \
9 2
/ \ \
3 5 7 */
Node root = null;
root = newNode(4);
root.left = newNode(9);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(7);
Vector<Integer> res = largestValues(root);
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i)+" ");
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python program to find largest value # on each level of binary tree. """ Recursive function to find the largest value on each level """ def helper(res, root, d): if ( not root): return # Expand list size if (d == len(res)): res.append(root.val) else: # to ensure largest value # on level is being stored res[d] = max(res[d], root.val) # Recursively traverse left and # right subtrees in order to find # out the largest value on each level helper(res, root.left, d + 1) helper(res, root.right, d + 1) # function to find largest values def largestValues(root): res = [] helper(res, root, 0) return res # Helper function that allocates a new # node with the given data and None left # and right pointers. class newNode: # Constructor to create a new node def __init__(self, data): self.val = data self.left = None self.right = None # Driver Code if __name__ == '__main__': """ Let us construct the following Tree 4 / \ 9 2 / \ \ 3 5 7 """ root = newNode(4) root.left = newNode(9) root.right = newNode(2) root.left.left = newNode(3) root.left.right = newNode(5) root.right.right = newNode(7) print(*largestValues(root)) # This code is contributed # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to find largest
// value on each level of binary tree.
using System;
using System.Collections.Generic;
class GFG
{
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
public class Node
{
public int val;
public Node left, right;
};
/* Recursive function to find
the largest value on each level */
static void helper(List<int> res,
Node root, int d)
{
if (root == null)
return;
// Expand list size
if (d == res.Count)
res.Add(root.val);
else
// to ensure largest value
// on level is being stored
res[d] = Math.Max(res[d], root.val);
// Recursively traverse left and
// right subtrees in order to find
// out the largest value on each level
helper(res, root.left, d + 1);
helper(res, root.right, d + 1);
}
// function to find largest values
static List<int> largestValues(Node root)
{
List<int> res = new List<int>();
helper(res, root, 0);
return res;
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void Main(String[] args)
{
/* Let us construct a Binary Tree
4
/ \
9 2
/ \ \
3 5 7 */
Node root = null;
root = newNode(4);
root.left = newNode(9);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(7);
List<int> res = largestValues(root);
for (int i = 0; i < res.Count; i++)
Console.Write(res[i] + " ");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find largest
// value on each level of binary tree.
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.val = data;
}
}
/* Recursive function to find
the largest value on each level */
function helper(res, root, d)
{
if (root == null)
return;
// Expand list size
if (d == res.length)
res.push(root.val);
else
// to ensure largest value
// on level is being stored
res[d] = Math.max(res[d], root.val);
// Recursively traverse left and
// right subtrees in order to find
// out the largest value on each level
helper(res, root.left, d + 1);
helper(res, root.right, d + 1);
}
// function to find largest values
function largestValues(root)
{
let res = [];
helper(res, root, 0);
return res;
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
function newNode(data)
{
let temp = new Node(data);
return temp;
}
/* Let us construct a Binary Tree
4
/ \
9 2
/ \ \
3 5 7 */
let root = null;
root = newNode(4);
root.left = newNode(9);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(7);
let res = largestValues(root);
for (let i = 0; i < res.length; i++)
document.write(res[i]+" ");
</script>