Cuente los Nodes que tienen el valor más alto en la ruta desde la raíz hasta sí mismo en un árbol binario

Dado un árbol binario , la tarea es contar el número de Nodes en el árbol binario, que son el Node de mayor valor en la ruta desde la raíz hasta ese Node.

Ejemplos:

Entrada: A continuación se muestra el Árbol dado:
       3
       / \
     2 5
   / \
  4 6
Salida: 4
Explicación:
El Node raíz cumple la condición requerida.
El Node 5 es el Node de mayor valor en la ruta (3 -> 5).
El Node 6 es el Node de mayor valor en la ruta (3 -> 5 -> 6).
El Node 4 es el Node de mayor valor en la ruta (3 -> 2 -> 4).
Por lo tanto, hay un total de 4 de estos Nodes en el árbol binario dado.

Entrada: A continuación se muestra el árbol dado:
         3
       / \
    1 2
   / \
 4 6 
Salida: 3 
 

Enfoque: la idea es realizar un recorrido en orden del árbol binario dado y actualizar el Node de valor máximo obtenido hasta ahora en la ruta después de cada llamada recursiva . Siga los pasos a continuación:

• Realizar un recorrido en orden en el árbol binario dado
• Después de cada llamada recursiva, actualice el Node de valor máximo encontrado hasta ahora en la ruta desde el Node raíz hasta el Node actual.
• Si el valor del Node excede el valor máximo del Node en la ruta hasta el momento, aumente el conteo en 1 y actualice el valor máximo obtenido hasta el momento.
• Continúe con los subárboles del Node actual.
• Después de completar el recorrido del Árbol Binario, imprima el conteo obtenido.

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

// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores the ct of
// nodes which are maximum
// in the path from root
// to the current node
int ct = 0;
 
// Binary Tree Node
struct Node
{
    int val;
    Node *left, *right;
     
    Node(int x)
    {
        val = x;
        left = right = NULL;
    }
};
 
// Function that performs Inorder
// Traversal on the Binary Tree
void find(Node *root, int mx)
{
     
    // If root does not exist
    if (root == NULL)
      return;
     
    // Check if the node
    // satisfies the condition
    if (root->val >= mx)
        ct++;
     
    // Update the maximum value
    // and recursively traverse
    // left and right subtree
    find(root->left, max(mx, root->val));
     
    find(root->right, max(mx, root->val));
}
 
// Function that counts the good
// nodes in the given Binary Tree
int NodesMaxInPath(Node* root)
{
     
    // Perform inorder Traversal
    find(root, INT_MIN);
     
    // Return the final count
    return ct;
}
 
// Driver code
int main()
{
     
    /* A Binary Tree
              3
             / \
            2   5
           /     \
          4       6
        */
    Node* root = new Node(3);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(4);
    root->right->right = new Node(7);
     
    // Function call
    int answer = NodesMaxInPath(root);
     
    // Print the count of good nodes
    cout << (answer);
    return 0;
}
 
// This code is contributed by mohit kumar 29

// Java program for the above approach
import java.util.*;
 
class GfG {
 
    // Stores the count of
    // nodes which are maximum
    // in the path from root
    // to the current node
    static int count = 0;
 
    // Binary Tree Node
    static class Node {
        int val;
        Node left, right;
    }
 
    // Function that performs Inorder
    // Traversal on the Binary Tree
    static void find(Node root, int max)
    {
        // If root does not exist
        if (root == null)
            return;
 
        // Check if the node
        // satisfies the condition
        if (root.val >= max)
            count++;
 
        // Update the maximum value
        // and recursively traverse
        // left and right subtree
        find(root.left,
             Math.max(max, root.val));
 
        find(root.right,
             Math.max(max, root.val));
    }
 
    // Function that counts the good
    // nodes in the given Binary Tree
    static int NodesMaxInPath(Node root)
    {
        // Perform inorder Traversal
        find(root, Integer.MIN_VALUE);
 
        // Return the final count
        return count;
    }
 
    // Function that add the new node
    // in the Binary Tree
    static Node newNode(int data)
    {
        Node temp = new Node();
        temp.val = data;
        temp.left = null;
        temp.right = null;
 
        // Return the node
        return temp;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        /* A Binary Tree
              3
             / \
            2   5
           /     \
          4       6
        */
 
        Node root = null;
        root = newNode(3);
        root.left = newNode(2);
        root.right = newNode(5);
        root.left.left = newNode(4);
        root.right.right = newNode(7);
 
        // Function Call
        int answer = NodesMaxInPath(root);
 
        // Print the count of good nodes
        System.out.println(answer);
    }
}

# Python 3 program for the
# above approach
import sys
 
# Stores the ct of
# nodes which are maximum
# in the path from root
# to the current node
ct = 0
 
# Binary Tree Node
class newNode:
   
    def __init__(self, x):
       
        self.val = x
        self.left = None
        self.right = None
 
# Function that performs Inorder
# Traversal on the Binary Tree
def find(root, mx):
   
    global ct
     
    # If root does not exist
    if (root == None):
        return
     
    # Check if the node
    # satisfies the condition
    if (root.val >= mx):
        ct += 1
     
    # Update the maximum value
    # and recursively traverse
    # left and right subtree
    find(root.left,
         max(mx, root.val))
     
    find(root.right,
         max(mx, root.val))
 
# Function that counts
# the good nodes in the
# given Binary Tree
def NodesMaxInPath(root):
   
    global ct
     
    # Perform inorder
    # Traversal
    find(root,
         -sys.maxsize-1)
     
    # Return the final count
    return ct
 
# Driver code
if __name__ == '__main__':
   
    '''
    /* A Binary Tree
              3
             / /
            2   5
           /     /
          4       6
        */
    '''
    root = newNode(3)
    root.left = newNode(2)
    root.right = newNode(5)
    root.left.left = newNode(4)
    root.right.right = newNode(7)
     
    # Function call
    answer = NodesMaxInPath(root)
     
    # Print the count of good nodes
    print(answer)
 
# This code is contributed by Surendra_Gangwar

// C# program for
// the above approach
using System;
class GfG{
 
// Stores the count of
// nodes which are maximum
// in the path from root
// to the current node
static int count = 0;
 
// Binary Tree Node
public class Node
{
  public int val;
  public Node left,
              right;
}
 
// Function that performs
// Inorder Traversal on
// the Binary Tree
static void find(Node root,
                 int max)
{
  // If root does not exist
  if (root == null)
    return;
 
  // Check if the node
  // satisfies the condition
  if (root.val >= max)
    count++;
 
  // Update the maximum value
  // and recursively traverse
  // left and right subtree
  find(root.left,
  Math.Max(max, root.val));
 
  find(root.right,
  Math.Max(max, root.val));
}
 
    // Function that counts the good
    // nodes in the given Binary Tree
    static int NodesMaxInPath(Node root)
    {
        // Perform inorder Traversal
        find(root, int.MinValue);
 
        // Return the readonly count
        return count;
    }
 
// Function that add the new node
// in the Binary Tree
static Node newNode(int data)
{
  Node temp = new Node();
  temp.val = data;
  temp.left = null;
  temp.right = null;
 
  // Return the node
  return temp;
}
 
// Driver Code
public static void Main(String[] args)
{
  /* A Binary Tree
              3
             / \
            2   5
           /     \
          4       6
        */
 
  Node root = null;
  root = newNode(3);
  root.left = newNode(2);
  root.right = newNode(5);
  root.left.left = newNode(4);
  root.right.right = newNode(7);
 
  // Function Call
  int answer = NodesMaxInPath(root);
 
  // Print the count of good nodes
  Console.WriteLine(answer);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program for the above approach
 
// Stores the count of
// nodes which are maximum
// in the path from root
// to the current node
let count = 0;
 
// Binary Tree Node
class Node
{
    constructor(data)
    {
        this.left = null;
        this.right = null;
        this.val = data;
    }
}
 
// Function that add the new node
// in the Binary Tree
function newNode(data)
{
    let temp = new Node(data);
     
    // Return the node
    return temp;
}
 
// Function that performs Inorder
// Traversal on the Binary Tree
function find(root, max)
{
     
    // If root does not exist
    if (root == null)
        return;
     
    // Check if the node
    // satisfies the condition
    if (root.val >= max)
        count++;
     
    // Update the maximum value
    // and recursively traverse
    // left and right subtree
    find(root.left, Math.max(max, root.val));
     
    find(root.right, Math.max(max, root.val));
}
 
// Function that counts the good
// nodes in the given Binary Tree
function NodesMaxInPath(root)
{
     
    // Perform inorder Traversal
    find(root, Number.MIN_VALUE);
     
    // Return the final count
    return count;
}
 
// Driver code
 
/* A Binary Tree
     3
    / \
   2   5
  /     \
 4       6
*/
 
let root = null;
root = newNode(3);
root.left = newNode(2);
root.right = newNode(5);
root.left.left = newNode(4);
root.right.right = newNode(7);
 
// Function Call
let answer = NodesMaxInPath(root);
 
// Print the count of good nodes
document.write(answer);  
 
// This code is contributed by suresh07
 
</script>

4

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