Dado un árbol binario, encuentre la suma de las alturas de todos los Nodes individuales en el árbol.
Ejemplo:
For this tree: 1). Height of Node 1 - 3 2). Height of Node 2 - 2 3). Height of Node 3 - 1 4). Height of Node 4 - 1 5). Height of Node 5 - 1 Adding all of them = 8
Prerrequisitos:- Altura del árbol binario
Solución simple:
Obtenemos la altura de todos los Nodes individuales al analizar el árbol en cualquiera de los siguientes métodos, es decir, Inorder, postorder, preorder (realicé el recorrido del árbol en orden) y obtener sus alturas usando la función getHeigh t, que verifica tanto el subárbol izquierdo como el derecho y devuelve el máximo de ellos. Finalmente, sumamos todas las alturas individuales.
C++
// C++ program to find sum of heights of all
// nodes in a binary tree
#include <bits/stdc++.h>
/* 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;
};
/* Compute the "maxHeight" of a particular Node*/
int getHeight(struct Node* Node)
{
if (Node == NULL)
return 0;
else {
/* compute the height of each subtree */
int lHeight = getHeight(Node->left);
int rHeight = getHeight(Node->right);
/* use the larger one */
if (lHeight > rHeight)
return (lHeight + 1);
else
return (rHeight + 1);
}
}
/* 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 = (struct Node*)
malloc(sizeof(struct Node));
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
/* Function to sum of heights of individual Nodes
Uses Inorder traversal */
int getTotalHeight(struct Node* root)
{
if (root == NULL)
return 0;
return getTotalHeight(root->left) +
getHeight(root) +
getTotalHeight(root->right);
}
// Driver code
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Sum of heights of all Nodes = %d",
getTotalHeight(root));
return 0;
}
Java
// Java program to find sum of heights of all
// nodes in a binary tree
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;
}
/* Compute the "maxHeight" of a particular Node*/
static int getHeight(Node Node)
{
if (Node == null)
return 0;
else {
/* compute the height of each subtree */
int lHeight = getHeight(Node.left);
int rHeight = getHeight(Node.right);
/* use the larger one */
if (lHeight > rHeight)
return (lHeight + 1);
else
return (rHeight + 1);
}
}
/* 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 sum of heights of individual Nodes
Uses Inorder traversal */
static int getTotalHeight( Node root)
{
if (root == null)
return 0;
return getTotalHeight(root.left) + getHeight(root) + getTotalHeight(root.right);
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
System.out.println("Sum of heights of all Nodes = " + getTotalHeight(root));
}
}
Python3
# Python3 program to find sum of heights
# of all nodes in a binary tree
# 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
# Compute the "maxHeight" of a
# particular Node
def getHeight(Node):
if (Node == None):
return 0
else:
# compute the height of each subtree
lHeight = getHeight(Node.left)
rHeight = getHeight(Node.right)
# use the larger one
if (lHeight > rHeight):
return (lHeight + 1)
else:
return (rHeight + 1)
# Function to sum of heights of
# individual Nodes Uses Inorder traversal
def getTotalHeight(root):
if (root == None):
return 0
return (getTotalHeight(root.left) +
getHeight(root) +
getTotalHeight(root.right))
# Driver code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
print("Sum of heights of all Nodes =",
getTotalHeight(root))
# This code is contributed by PranchalK
C#
// C# program to find sum of heights of all
// nodes in a binary tree
using System;
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;
}
/* Compute the "maxHeight" of a particular Node*/
static int getHeight(Node Node)
{
if (Node == null)
return 0;
else
{
/* compute the height of each subtree */
int lHeight = getHeight(Node.left);
int rHeight = getHeight(Node.right);
/* use the larger one */
if (lHeight > rHeight)
return (lHeight + 1);
else
return (rHeight + 1);
}
}
/* 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 sum of heights of individual Nodes
Uses Inorder traversal */
static int getTotalHeight( Node root)
{
if (root == null)
return 0;
return getTotalHeight(root.left) +
getHeight(root) +
getTotalHeight(root.right);
}
// Driver code
public static void Main(String []args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
Console.Write("Sum of heights of all Nodes = " + getTotalHeight(root));
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// Javascript program to find sum of heights of all
// nodes in a binary tree
/* A binary tree Node has data, pointer to
left child and a pointer to right child */
class Node
{
constructor(data)
{
this.data=data;
this.left=this.right=null;
}
}
/* Compute the "maxHeight" of a particular Node*/
function getHeight(Node)
{
if (Node == null)
return 0;
else {
/* compute the height of each subtree */
let lHeight = getHeight(Node.left);
let rHeight = getHeight(Node.right);
/* use the larger one */
if (lHeight > rHeight)
return (lHeight + 1);
else
return (rHeight + 1);
}
}
/* Function to sum of heights of individual Nodes
Uses Inorder traversal */
function getTotalHeight(root)
{
if (root == null)
return 0;
return getTotalHeight(root.left) + getHeight(root) + getTotalHeight(root.right);
}
// Driver code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("Sum of heights of all Nodes = " + getTotalHeight(root));
// This code is contributed by patel2127
</script>
Producción:
Sum of heights of all Nodes = 8
Complejidad temporal: O(nh) donde n es el número total de Nodes yh es la altura del árbol binario.
Solución eficiente:
La idea es calcular alturas y resumirlas en la misma llamada recursiva.
C++
// C++ program to find sum of heights of all
// nodes in a 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 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 = (struct Node*)
malloc(sizeof(struct Node));
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
/* Function to sum of heights of individual Nodes
Uses Inorder traversal */
int getTotalHeightUtil(struct Node* root, int &sum)
{
if (root == NULL)
return 0;
int lh = getTotalHeightUtil(root->left, sum);
int rh = getTotalHeightUtil(root->right, sum);
int h = max(lh, rh) + 1;
sum = sum + h;
return h;
}
int getTotalHeight(Node *root)
{
int sum = 0;
getTotalHeightUtil(root, sum);
return sum;
}
// Driver code
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Sum of heights of all Nodes = %d",
getTotalHeight(root));
return 0;
}
Java
// Java program to find sum of heights of all
// nodes in a binary tree
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;
};
static int sum;
/* 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 sum of heights of individual Nodes
Uses Inorder traversal */
static int getTotalHeightUtil(Node root)
{
if (root == null)
{
return 0;
}
int lh = getTotalHeightUtil(root.left);
int rh = getTotalHeightUtil(root.right);
int h = Math.max(lh, rh) + 1;
sum = sum + h;
return h;
}
static int getTotalHeight(Node root)
{
sum = 0;
getTotalHeightUtil(root);
return sum;
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
System.out.printf("Sum of heights of all Nodes = %d",
getTotalHeight(root));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find sum of heights
# of all nodes in a binary tree
# A binary tree Node has data, pointer to
# left child and a pointer to right child
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
sum = 0
# Function to sum of heights of individual
# Nodes Uses Inorder traversal
def getTotalHeightUtil(root):
global sum
if (root == None):
return 0
lh = getTotalHeightUtil(root.left)
rh = getTotalHeightUtil(root.right)
h = max(lh, rh) + 1
sum = sum + h
return h
def getTotalHeight(root):
getTotalHeightUtil(root)
return sum
# Driver code
if __name__ == '__main__':
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Sum of heights of all Nodes =",
getTotalHeight(root))
# This code is contributed by mohit kumar 29
C#
// C# program to find sum of heights of
// all nodes in a 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 */
class Node
{
public int data;
public Node left;
public Node right;
};
static int sum;
/* 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 sum of heights of
individual Nodes Uses Inorder traversal */
static int getTotalHeightUtil(Node root)
{
if (root == null)
{
return 0;
}
int lh = getTotalHeightUtil(root.left);
int rh = getTotalHeightUtil(root.right);
int h = Math.Max(lh, rh) + 1;
sum = sum + h;
return h;
}
static int getTotalHeight(Node root)
{
sum = 0;
getTotalHeightUtil(root);
return sum;
}
// Driver code
public static void Main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
Console.Write("Sum of heights of all Nodes = {0}",
getTotalHeight(root));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to find sum of heights of all
// nodes in a binary tree
/* A binary tree Node has data, pointer to
left child and a pointer to right child */
class Node
{
constructor(data)
{
this.data=data;
this.left=this.right=null;
}
}
let sum;
/* Function to sum of heights of individual Nodes
Uses Inorder traversal */
function getTotalHeightUtil(root)
{
if (root == null)
{
return 0;
}
let lh = getTotalHeightUtil(root.left);
let rh = getTotalHeightUtil(root.right);
let h = Math.max(lh, rh) + 1;
sum = sum + h;
return h;
}
function getTotalHeight(root)
{
sum = 0;
getTotalHeightUtil(root);
return sum;
}
// Driver code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("Sum of heights of all Nodes = ",
getTotalHeight(root));
// This code is contributed by unknown2108
</script>
Producción:
Sum of heights of all Nodes = 8
Complejidad temporal: O(n) donde n es el número total de Nodes del árbol binario.
Publicación traducida automáticamente
Artículo escrito por Sakshi_Tiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA