Dado un árbol binario, encuentre la suma de todas las hojas correctas en él.
Artículo similar: encuentre la suma de todas las hojas restantes en un árbol binario dado
Ejemplo :
C++
// CPP program to find total sum
// of right leaf nodes
#include <bits/stdc++.h>
using namespace std;
// struct node of binary tree
struct Node{
int data;
Node *left, *right;
};
// return new node
Node *addNode(int data){
Node *temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
}
// utility function to calculate sum
// of right leaf nodes
void rightLeafSum(Node *root, int *sum){
if(!root)
return;
// check if the right child of root
// is leaf node
if(root->right)
if(!root->right->left &&
!root->right->right)
*sum += root->right->data;
rightLeafSum(root->left, sum);
rightLeafSum(root->right, sum);
}
// driver program
int main(){
//construct binary tree
Node *root = addNode(1);
root->left = addNode(2);
root->left->left = addNode(4);
root->left->right = addNode(5);
root->left->left->right = addNode(2);
root->right = addNode(3);
root->right->right = addNode(8);
root->right->right->left = addNode(6);
root->right->right->right = addNode(7);
// variable to store sum of right
// leaves
int sum = 0;
rightLeafSum(root, &sum);
cout << sum << endl;
return 0;
}
Java
// Java program to find total
// sum of right leaf nodes
class GFG
{
// sum
static int sum = 0;
// node of binary tree
static class Node
{
int data;
Node left, right;
};
// return new node
static Node addNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// utility function to calculate
// sum of right leaf nodes
static void rightLeafSum(Node root)
{
if(root == null)
return;
// check if the right child
// of root is leaf node
if(root.right != null)
if(root.right.left == null &&
root.right.right == null)
sum += root.right.data;
rightLeafSum(root.left);
rightLeafSum(root.right);
}
// Driver Code
public static void main(String args[])
{
//construct binary tree
Node root = addNode(1);
root.left = addNode(2);
root.left.left = addNode(4);
root.left.right = addNode(5);
root.left.left.right = addNode(2);
root.right = addNode(3);
root.right.right = addNode(8);
root.right.right.left = addNode(6);
root.right.right.right = addNode(7);
// variable to store sum
// of right leaves
sum = 0;
rightLeafSum(root);
System.out.println( sum );
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find total Sum # of right leaf nodes # return new node class addNode: def __init__(self, data): self.data = data self.left = self.right = None # utility function to calculate Sum # of right leaf nodes def rightLeafSum(root, Sum): if(not root): return # check if the right child of root # is leaf node if(root.right): if(not root.right.left and not root.right.right): Sum[0] += root.right.data rightLeafSum(root.left, Sum) rightLeafSum(root.right, Sum) # Driver Code if __name__ == '__main__': # construct binary tree root = addNode(1) root.left = addNode(2) root.left.left = addNode(4) root.left.right = addNode(5) root.left.left.right = addNode(2) root.right = addNode(3) root.right.right = addNode(8) root.right.right.left = addNode(6) root.right.right.right = addNode(7) # variable to store Sum of right # leaves Sum = [0] rightLeafSum(root, Sum) print(Sum[0]) # This code is contributed by PranchalK
C#
using System;
// C# program to find total
// sum of right leaf nodes
public class GFG
{
// sum
public static int sum = 0;
// node of binary tree
public class Node
{
public int data;
public Node left, right;
}
// return new node
public static Node addNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// utility function to calculate
// sum of right leaf nodes
public static void rightLeafSum(Node root)
{
if (root == null)
{
return;
}
// check if the right child
// of root is leaf node
if (root.right != null)
{
if (root.right.left == null && root.right.right == null)
{
sum += root.right.data;
}
}
rightLeafSum(root.left);
rightLeafSum(root.right);
}
// Driver Code
public static void Main(string[] args)
{
//construct binary tree
Node root = addNode(1);
root.left = addNode(2);
root.left.left = addNode(4);
root.left.right = addNode(5);
root.left.left.right = addNode(2);
root.right = addNode(3);
root.right.right = addNode(8);
root.right.right.left = addNode(6);
root.right.right.right = addNode(7);
// variable to store sum
// of right leaves
sum = 0;
rightLeafSum(root);
Console.WriteLine(sum);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find total
// sum of right leaf nodes
// sum
let sum = 0;
// node of binary tree
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// return new node
function addNode(data)
{
let temp = new Node(data);
return temp;
}
// utility function to calculate
// sum of right leaf nodes
function rightLeafSum(root)
{
if(root == null)
return;
// check if the right child
// of root is leaf node
if(root.right != null)
if(root.right.left == null &&
root.right.right == null)
sum += root.right.data;
rightLeafSum(root.left);
rightLeafSum(root.right);
}
//construct binary tree
let root = addNode(1);
root.left = addNode(2);
root.left.left = addNode(4);
root.left.right = addNode(5);
root.left.left.right = addNode(2);
root.right = addNode(3);
root.right.right = addNode(8);
root.right.right.left = addNode(6);
root.right.right.right = addNode(7);
// variable to store sum
// of right leaves
sum = 0;
rightLeafSum(root);
document.write(sum );
// This code is contributed by divyesh072019.
</script>
C++
// CPP program to find total sum
// of right leaf nodes
#include <bits/stdc++.h>
using namespace std;
// struct node of binary tree
struct Node {
int data;
Node *left, *right;
};
// return new node
Node* addNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// utility function to calculate sum
// of right leaf nodes iteratively
int rightLeafSum(Node* root)
{
// declaring sum to store sum of right leaves
int sum = 0;
// queue of Node* type
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
// check for left node
if (curr->left) {
q.push(curr->left);
}
// check for right node
if (curr->right) {
// check for right leaf node
if (curr->right->right == NULL
and curr->right->left == NULL) {
// incrementing sum for found right leaf
// node
sum += curr->right->data;
}
q.push(curr->right);
}
}
return sum;
}
// driver program
int main()
{
// construct binary tree
Node* root = addNode(1);
root->left = addNode(2);
root->left->left = addNode(4);
root->left->right = addNode(5);
root->left->left->right = addNode(2);
root->right = addNode(3);
root->right->right = addNode(8);
root->right->right->left = addNode(6);
root->right->right->right = addNode(7);
int sum = rightLeafSum(root);
cout << sum << endl;
return 0;
}
Java
// Java program to find total sum
// of right leaf nodes
import java.io.*;
import java.util.*;
class Node {
int data;
Node left, right;
Node(int data)
{
this.left = null;
this.right = null;
this.data = data;
}
}
class GFG {
// return new node
static Node addNode(int data)
{
Node temp = new Node(data);
return temp;
}
// utility function to calculate sum
// of right leaf nodes iteratively
static int rightLeafSum(Node root)
{
// declaring sum to store sum of right leaves
int sum = 0;
// queue of Node* type
Queue<Node> q = new LinkedList<>();
q.add(root);
while (q.size() > 0) {
Node curr = q.peek();
q.remove();
// check for left node
if (curr.left != null) {
q.add(curr.left);
}
// check for right node
if (curr.right != null) {
// check for right leaf node
if (curr.right.right == null
&& curr.right.left == null) {
// incrementing sum for found right leaf
// node
sum += curr.right.data;
}
q.add(curr.right);
}
}
return sum;
}
// construct binary tree
public static void main(String[] args)
{
Node root = addNode(1);
root.left = addNode(2);
root.left.left = addNode(4);
root.left.right = addNode(5);
root.left.left.right = addNode(2);
root.right = addNode(3);
root.right.right = addNode(8);
root.right.right.left = addNode(6);
root.right.right.right = addNode(7);
int sum = rightLeafSum(root);
System.out.println(sum);
}
}
// This code is contributed by avanitrachhadiya2155.
Python3
# Python3 program to find total sum # of right leaf nodes # Return new node class addNode: def __init__(self, data): self.data = data self.left = self.right = None # Utility function to calculate Sum # of right leaf nodes def rightLeafSum(root): # Declaring sum to store sum of right leaves sum = 0 # Queue of Node* type q = [] q.append(root) while (len(q) > 0): curr = q.pop(0) # Check for left node if (curr.left != None): q.append(curr.left) # Check for right node if (curr.right != None): # Check for right leaf node if (curr.right.right == None and curr.right.left == None): # Incrementing sum for found right leaf # node sum += curr.right.data q.append(curr.right) return sum # Driver Code if __name__ == '__main__': # construct binary tree root = addNode(1) root.left = addNode(2) root.left.left = addNode(4) root.left.right = addNode(5) root.left.left.right = addNode(2) root.right = addNode(3) root.right.right = addNode(8) root.right.right.left = addNode(6) root.right.right.right = addNode(7) # variable to store Sum of right # leaves sum = rightLeafSum(root) print(sum) # This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to find total sum
// of right leaf nodes
using System;
using System.Collections.Generic;
public
class Node {
public
int data;
public
Node left,
right;
public
Node(int data)
{
this.left = null;
this.right = null;
this.data = data;
}
}
public class GFG {
// return new node
static Node addNode(int data)
{
Node temp = new Node(data);
return temp;
}
// utility function to calculate sum
// of right leaf nodes iteratively
static int rightLeafSum(Node root)
{
// declaring sum to store sum of right leaves
int sum = 0;
// queue of Node* type
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0) {
Node curr = q.Peek();
q.Dequeue();
// check for left node
if (curr.left != null) {
q.Enqueue(curr.left);
}
// check for right node
if (curr.right != null) {
// check for right leaf node
if (curr.right.right == null
&& curr.right.left == null) {
// incrementing sum for found right leaf
// node
sum += curr.right.data;
}
q.Enqueue(curr.right);
}
}
return sum;
}
// construct binary tree
public static void Main(String[] args)
{
Node root = addNode(1);
root.left = addNode(2);
root.left.left = addNode(4);
root.left.right = addNode(5);
root.left.left.right = addNode(2);
root.right = addNode(3);
root.right.right = addNode(8);
root.right.right.left = addNode(6);
root.right.right.right = addNode(7);
int sum = rightLeafSum(root);
Console.WriteLine(sum);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript program to find total sum
// of right leaf nodes
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// return new node
function addNode(data)
{
let temp = new Node(data);
return temp;
}
// utility function to calculate sum
// of right leaf nodes iteratively
function rightLeafSum(root)
{
// declaring sum to store sum of right leaves
let sum = 0;
// queue of Node* type
let q = [];
q.push(root);
while (q.length > 0) {
let curr = q[0];
q.shift();
// check for left node
if (curr.left != null) {
q.push(curr.left);
}
// check for right node
if (curr.right) {
// check for right leaf node
if (curr.right.right == null
&& curr.right.left == null) {
// incrementing sum for found right leaf
// node
sum += curr.right.data;
}
q.push(curr.right);
}
}
return sum;
}
// construct binary tree
let root = addNode(1);
root.left = addNode(2);
root.left.left = addNode(4);
root.left.right = addNode(5);
root.left.left.right = addNode(2);
root.right = addNode(3);
root.right.right = addNode(8);
root.right.right.left = addNode(6);
root.right.right.right = addNode(7);
let sum = rightLeafSum(root);
document.write(sum);
</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