Encuentre la suma de todos los Nodes de la hoja izquierda que también tiene su hermano derecho

Posted on by Rudeus Greyrat

Dado un árbol binario enraizado en la raíz , la tarea es encontrar la suma de todos los Nodes de hoja que son hijos izquierdos de sus padres y que también tienen su hermano derecho, es decir, es un padre que también tiene un hijo derecho.

Ejemplos :

Entrada:          16
                 / \
            20 15
           / / \
     100 21 25
     / / \ / \
27 14 9 7 6
          / \ \
     17    12 2
Salida: 24.
Explicación: Los Nodes hoja que tienen los valores 7 y 17 solo tienen un hermano derecho.

Entrada:               12
                      / \
                  13 10
                          / \
                      14 15
                             / \
                          22 23 

Salida: 49

 

Enfoque: La idea es utilizar la recursividad para resolver este problema. Comience a atravesar desde el Node raíz. Para cada Node, verifique si es NULL si es verdadero, luego devuelva 0. Si ambos elementos secundarios son NULL , devuelva 0 . Si ambos hijos no son NULL :

  • Si la izquierda es un Node de hoja, devuelva root->left->data + value al atravesar el elemento secundario derecho.
  • De lo contrario, el valor devuelto se obtiene al atravesar el elemento secundario izquierdo + el valor se obtiene al atravesar el elemento secundario derecho

Siguiendo los pasos a continuación para resolver el problema:

  • Si raíz es igual a nulo o un Node hoja, devuelve 0.
  • Si root tiene ambos hijos, realice las siguientes tareas:
    • Si el hijo izquierdo de la raíz es un Node hoja, devuelva root->left->data + sumOfLeft(root->right).
    • De lo contrario, devuelve la suma de sumofLeft(root->left) y sumofLeft(root->right).
  • De lo contrario, si hay root->left, devuelve sumofLeft(root->left).
  • De lo contrario, devuelve sumofLeft (raíz-> derecha).

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of the binary tree.
class Node {
public:
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
 
// Function to return the sum of
// left leaf node having right sibling.
int sumOfLeft(Node* root)
{
 
    // If root node is NULL
    if (root == NULL)
        return 0;
 
    // If root node is a leaf node
    // Note: It is not for left leaf
    // node having right sibling
    if (root->left == NULL
        && root->right == NULL)
        return 0;
 
    // If node has both the child
    if (root->left != NULL
        && root->right != NULL) {
 
        // If its left node is leaf node
        if (root->left->left == NULL
            && root->left->right == NULL) {
 
            // Returning the sum of
            // left node data
            // and the value obtained by
            // traversing right child
            return root->left->data
                   + sumOfLeft(root->right);
        }
        else {
 
            // Returning sum of values
            // obtained by traversing
            // both the child
            return sumOfLeft(root->left)
                   + sumOfLeft(root->right);
        }
    }
 
    // If there is only left child
    else if (root->left != NULL) {
        return sumOfLeft(root->left);
    }
 
    // If only right child is left
    return sumOfLeft(root->right);
}
 
// Driver Code
int main()
{
    // Binary tree construction
    Node* root = new Node(12);
    root->left = new Node(13);
    root->right = new Node(10);
    root->right->left = new Node(14);
    root->right->right = new Node(15);
    root->right->right->left
        = new Node(22);
    root->right->right->right
        = new Node(23);
    cout << sumOfLeft(root);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Node of the binary tree.
static class Node {
    int data;
    Node left, right;
    Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Function to return the sum of
// left leaf node having right sibling.
static int sumOfLeft(Node root)
{
 
    // If root node is null
    if (root == null)
        return 0;
 
    // If root node is a leaf node
    // Note: It is not for left leaf
    // node having right sibling
    if (root.left == null
        && root.right == null)
        return 0;
 
    // If node has both the child
    if (root.left != null
        && root.right != null) {
 
        // If its left node is leaf node
        if (root.left.left == null
            && root.left.right == null) {
 
            // Returning the sum of
            // left node data
            // and the value obtained by
            // traversing right child
            return root.left.data
                   + sumOfLeft(root.right);
        }
        else {
 
            // Returning sum of values
            // obtained by traversing
            // both the child
            return sumOfLeft(root.left)
                   + sumOfLeft(root.right);
        }
    }
 
    // If there is only left child
    else if (root.left != null) {
        return sumOfLeft(root.left);
    }
 
    // If only right child is left
    return sumOfLeft(root.right);
}
 
// Driver Code
public static void main(String[] args)
{
    // Binary tree construction
    Node root = new Node(12);
    root.left = new Node(13);
    root.right = new Node(10);
    root.right.left = new Node(14);
    root.right.right = new Node(15);
    root.right.right.left
        = new Node(22);
    root.right.right.right
        = new Node(23);
    System.out.print(sumOfLeft(root));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for the above approach
 
# Node of the binary tree.
class Node:
    def __init__(self, data):
        self.data = data;
        self.left = None;
        self.right = None;
 
# Function to return the sum of
# left leaf Node having right sibling.
def sumOfLeft(root):
 
    # If root Node is None
    if (root == None):
        return 0;
 
    # If root Node is a leaf Node
    # Note: It is not for left leaf
    # Node having right sibling
    if (root.left == None and root.right == None):
        return 0;
 
    # If Node has both the child
    if (root.left != None and root.right != None):
 
        # If its left Node is leaf Node
        if (root.left.left == None and root.left.right == None):
 
            # Returning the sum of
            # left Node data
            # and the value obtained by
            # traversing right child
            return root.left.data + sumOfLeft(root.right);
        else:
 
            # Returning sum of values
            # obtained by traversing
            # both the child
            return sumOfLeft(root.left) + sumOfLeft(root.right);
         
    # If there is only left child
    elif(root.left != None):
        return sumOfLeft(root.left);
     
    # If only right child is left
    return sumOfLeft(root.right);
 
# Driver Code
if __name__ == '__main__':
   
    # Binary tree construction
    root =  Node(12);
    root.left =  Node(13);
    root.right =  Node(10);
    root.right.left =  Node(14);
    root.right.right =  Node(15);
    root.right.right.left =  Node(22);
    root.right.right.right =  Node(23);
    print(sumOfLeft(root));
 
# This code is contributed by Rajput-Ji

C#

// C# program for the above approach
using System;
public class GFG{
 
  // Node of the binary tree.
  class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
      this.data = data;
      this.left = null;
      this.right = null;
    }
  };
 
  // Function to return the sum of
  // left leaf node having right sibling.
  static int sumOfLeft(Node root)
  {
 
    // If root node is null
    if (root == null)
      return 0;
 
    // If root node is a leaf node
    // Note: It is not for left leaf
    // node having right sibling
    if (root.left == null
        && root.right == null)
      return 0;
 
    // If node has both the child
    if (root.left != null
        && root.right != null) {
 
      // If its left node is leaf node
      if (root.left.left == null
          && root.left.right == null) {
 
        // Returning the sum of
        // left node data
        // and the value obtained by
        // traversing right child
        return root.left.data
          + sumOfLeft(root.right);
      }
      else {
 
        // Returning sum of values
        // obtained by traversing
        // both the child
        return sumOfLeft(root.left)
          + sumOfLeft(root.right);
      }
    }
 
    // If there is only left child
    else if (root.left != null) {
      return sumOfLeft(root.left);
    }
 
    // If only right child is left
    return sumOfLeft(root.right);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Binary tree construction
    Node root = new Node(12);
    root.left = new Node(13);
    root.right = new Node(10);
    root.right.left = new Node(14);
    root.right.right = new Node(15);
    root.right.right.left
      = new Node(22);
    root.right.right.right
      = new Node(23);
    Console.Write(sumOfLeft(root));
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
       // JavaScript code for the above approach
 
       // Node of the binary tree.
       class Node {
 
           constructor(d) {
               this.data = d;
               this.left = null;
               this.right = null;
           }
       };
 
       // Function to return the sum of
       // left leaf node having right sibling.
       function sumOfLeft(root) {
 
           // If root node is null
           if (root == null)
               return 0;
 
           // If root node is a leaf node
           // Note: It is not for left leaf
           // node having right sibling
           if (root.left == null
               && root.right == null)
               return 0;
 
           // If node has both the child
           if (root.left != null
               && root.right != null) {
 
               // If its left node is leaf node
               if (root.left.left == null
                   && root.left.right == null) {
 
                   // Returning the sum of
                   // left node data
                   // and the value obtained by
                   // traversing right child
                   return root.left.data
                       + sumOfLeft(root.right);
               }
               else {
 
                   // Returning sum of values
                   // obtained by traversing
                   // both the child
                   return sumOfLeft(root.left)
                       + sumOfLeft(root.right);
               }
           }
 
           // If there is only left child
           else if (root.left != null) {
               return sumOfLeft(root.left);
           }
 
           // If only right child is left
           return sumOfLeft(root.right);
       }
 
       // Driver Code
 
       // Binary tree construction
       let root = new Node(12);
       root.left = new Node(13);
       root.right = new Node(10);
       root.right.left = new Node(14);
       root.right.right = new Node(15);
       root.right.right.left
           = new Node(22);
       root.right.right.right
           = new Node(23);
       document.write(sumOfLeft(root));
 
      // This code is contributed by Potta Lokesh
   </script>
Producción

49

Complejidad de Tiempo: O(N) donde N es el número total de Nodes
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ritwickbisht1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *