Suma de Nodes en un árbol binario que tiene solo los Nodes secundarios izquierdos

Dado un árbol binario , la tarea es encontrar la suma de los Nodes del árbol binario que tienen solo los Nodes secundarios izquierdos.

Ejemplo:

Entrada:      8
            / \
          3 7
        / \ /
      5 6 0
    //
  1 2
Salida: 18 Explicación: Los Nodes con valores 5, 6 y 7 son los que tienen solo los Nodes secundarios izquierdos 

Entrada:    2
           / \
        3 1
      / /
    5 6
Salida: 4

Enfoque: El problema dado se puede resolver recorriendo el árbol binario utilizando postorder traversal . La idea es verificar si un Node contiene solo un Node secundario izquierdo y agregar el valor del Node actual a la respuesta si la condición es verdadera. Se pueden seguir los siguientes pasos para resolver el problema:

• Atraviesa el árbol binario usando el recorrido posorden
  • Si la raíz es nula, devuelve 0
  • Use la recursividad en el subárbol izquierdo y almacene su respuesta en una variable izquierda
  • Use la recursividad en el subárbol derecho y almacene su respuesta en una variable a la derecha
  • Si root.left != null && root.right == null, devolver el valor de root.val + left + right
  • De lo contrario volver izquierda + derecha

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
struct Node
{
 
    int val;
    Node *left;
    Node *right;
    Node(int value)
    {
        val = value;
        left = NULL;
        right = NULL;
    }
};
 
// Function to find the sum of nodes
// having only left child node
int sumLeftChild(Node *root)
{
    if (root == NULL)
        return 0;
 
    // Sum of nodes having only left
    // child node from left subtree
    int left = sumLeftChild(root->left);
 
    // Sum of nodes having only left
    // child node from right subtree
    int right = sumLeftChild(root->right);
 
    // If current node has only left
    // child node return the sum from
    // left subtree + right
    // subtree + root->val
    if (root->left != NULL && root->right == NULL)
    {
 
        return root->val + left + right;
    }
 
    // Return the value from left
    // and right subtrees
    return left + right;
}
 
// Driver code
int main()
{
 
    // Initialize the tree
    Node *root = new Node(2);
    root->left = new Node(3);
    root->right = new Node(4);
    root->left->left = new Node(5);
    root->right->left = new Node(7);
    cout << (sumLeftChild(root));
    return 0;
}
 
// This code is contributed by Potta Lokesh

// Java implementation for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the sum of nodes
    // having only left child node
    public static int sumLeftChild(Node root)
    {
        if (root == null)
            return 0;
 
        // Sum of nodes having only left
        // child node from left subtree
        int left = sumLeftChild(root.left);
 
        // Sum of nodes having only left
        // child node from right subtree
        int right = sumLeftChild(root.right);
 
        // If current node has only left
        // child node return the sum from
        // left subtree + right
        // subtree + root.val
        if (root.left != null && root.right == null) {
 
            return root.val + left + right;
        }
 
        // Return the value from left
        // and right subtrees
        return left + right;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Initialize the tree
        Node root = new Node(2);
        root.left = new Node(3);
        root.right = new Node(4);
        root.left.left = new Node(5);
        root.right.left = new Node(7);
        System.out.println(sumLeftChild(root));
    }
 
    static class Node {
 
        int val;
        Node left, right;
        public Node(int val)
        {
            this.val = val;
        }
    }
}

// C# implementation for the above approach
using System;
 
public class GFG {
 
  // Function to find the sum of nodes
  // having only left child node
  public static int sumLeftChild(Node root) {
    if (root == null)
      return 0;
 
    // Sum of nodes having only left
    // child node from left subtree
    int left = sumLeftChild(root.left);
 
    // Sum of nodes having only left
    // child node from right subtree
    int right = sumLeftChild(root.right);
 
    // If current node has only left
    // child node return the sum from
    // left subtree + right
    // subtree + root.val
    if (root.left != null && root.right == null) {
 
      return root.val + left + right;
    }
 
    // Return the value from left
    // and right subtrees
    return left + right;
  }
 
  // Driver code
  public static void Main(String[] args) {
 
    // Initialize the tree
    Node root = new Node(2);
    root.left = new Node(3);
    root.right = new Node(4);
    root.left.left = new Node(5);
    root.right.left = new Node(7);
    Console.WriteLine(sumLeftChild(root));
  }
 
  public class Node {
 
    public int val;
    public Node left, right;
 
    public Node(int val) {
      this.val = val;
    }
  }
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript implementation for the above approach
 
class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
 
// Function to find the sum of nodes
// having only left child node
function sumLeftChild(root) {
  if (root == null)
    return 0;
 
  // Sum of nodes having only left
  // child node from left subtree
  let left = sumLeftChild(root.left);
 
  // Sum of nodes having only left
  // child node from right subtree
  let right = sumLeftChild(root.right);
 
  // If current node has only left
  // child node return the sum from
  // left subtree + right
  // subtree + root.val
  if (root.left != null && root.right == null) {
 
    return root.val + left + right;
  }
 
  // Return the value from left
  // and right subtrees
  return left + right;
}
 
// Driver code
 
// Initialize the tree
let root = new Node(2);
root.left = new Node(3);
root.right = new Node(4);
root.left.left = new Node(5);
root.right.left = new Node(7);
document.write(sumLeftChild(root));
 
// This code is contributed by saurabh_jaiswal.
</script>

7

Complejidad temporal: O(N)
Espacio auxiliar: O(1)