Dado un árbol binario dirigido de N Nodes cuyas aristas van del padre al hijo , la tarea es contar el número de caminos estrictamente crecientes y decrecientes.
Nota: un camino comienza en la raíz y termina en cualquier hoja.
Ejemplos:
Entrada: N = 6
árbol = 6
/ \
4 7
\ / \
5 6 8
Salida: 10 8
Explicación: Para el árbol binario anterior, los caminos estrictamente crecientes son:
Todos los caminos que consisten en un solo Node son = 6.
Los caminos que contienen dos Nodes son: 4->5, 7->8, 6->7 = 3.
Los caminos que contienen tres Nodes son: 6->7->8 = 1.
Por lo tanto, el número de caminos estrictamente crecientes es 6 + 3 + 1 = 10 .
Para el árbol binario anterior, los caminos estrictamente decrecientes son:
Todos los caminos que consisten en un solo Node son = 6.
Los caminos que contienen dos Nodes son: 6->4, 7->6 = 2.
Por lo tanto, la cuenta de caminos estrictamente decrecientes es 6 + 2 = 8 .Entrada: N = 5
árbol 15
/
8
\
2
/ \
13 9
Salida: 7 8
Explicación:
Para el árbol binario anterior, los caminos estrictamente crecientes son:
Todos los caminos que consisten en un solo Node son = 5.
Los caminos que contienen dos Nodes son: 2->9, 2->13 = 2.
Por lo tanto, la cuenta de caminos estrictamente crecientes es 5 + 2 = 7 .
Para el árbol binario anterior, los caminos estrictamente decrecientes son:
Todos los caminos que consisten en un solo Node son = 5.
Los caminos que contienen dos Nodes son: 15->8, 8->2 = 2.
Los caminos que contienen tres Nodes son: 15->8->2 = 1.
Por lo tanto, la cuenta de caminos estrictamente decrecientes es 5 + 2 + 1 = 8 .
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Si un camino que comienza desde cualquier Node u es estrictamente creciente y su valor es mayor que el valor de su padre (por ejemplo , v ), entonces todos los caminos estrictamente crecientes que comienzan desde u también son estrictamente crecientes cuando el Node inicial es v . Lo mismo es cierto en el caso de trayectorias estrictamente decrecientes.
A partir de la observación anterior, el problema se puede resolver con la ayuda de la recursividad . Siga los pasos a continuación para resolver el problema:
- Use una función recursiva para atravesar el árbol comenzando desde la raíz y para cada Node devuelva el recuento de rutas estrictamente crecientes y estrictamente decrecientes desde ese Node.
- En cada recursión:
- Compruebe si la ruta desde el Node actual hasta un hijo (izquierda o derecha) aumenta o disminuye.
- Llame a la función recursiva para el niño .
- Agregue el conteo de rutas crecientes o decrecientes al conteo total si la ruta desde el Node actual hasta el hijo es creciente o decreciente respectivamente.
- Devuelve el conteo final de camino creciente o decreciente obtenido para root.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Following is the TreeNode
// class structure:
template <typename T>
class TreeNode {
public:
T data;
TreeNode<T>* left;
TreeNode<T>* right;
TreeNode(T data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Helper function to get the answer
pair<int, int> countPathsHelper(TreeNode<int>* root,
int& increase,
int& decrease)
{
// If the root is NULL,
// then no strictly increasing or
// decreasing path.
if (root == NULL) {
return { 0, 0 };
}
// Call the function for both
// the left and right child.
pair<int, int> p1
= countPathsHelper(root->left,
increase, decrease);
pair<int, int> p2
= countPathsHelper(root->right,
increase, decrease);
// Initialize 'inc' and 'dec' to 1
int inc = 1, dec = 1;
// If the left child is not NULL.
if (root->left != NULL) {
// Check if the value is
// increasing from parent to child.
if (root->data < root->left->data) {
// Add the count of strictly
// increasing paths of
// child to parent.
inc += p1.first;
}
// Check if the value is decreasing
// from parent to child.
if (root->data > root->left->data) {
// Add the count of strictly
// decreasing paths of
// child to parent.
dec += p1.second;
}
}
if (root->right != NULL) {
// Check if the value is
// increasing from parent to child.
if (root->data < root->right->data) {
// Add the count of strictly
// increasing paths of
// child to parent.
inc += p2.first;
}
// Check if the value is
// decreasing from parent to child
if (root->data > root->right->data) {
// Add the count of strictly
// decreasing paths of
// child to parent.
dec += p2.second;
}
}
// Add the total count of
// strictly increasing paths to
// the global strictly increasing
// paths counter.
increase += inc;
// Add the total count of
// strictly decreasing paths to
// the global strictly
// decreasing paths counter.
decrease += dec;
return { inc, dec };
}
// Function to count the paths
pair<int, int> countPaths(TreeNode<int>* root)
{
// 'increase' stores the
// total strictly increasing paths.
int increase = 0;
// 'decrease' stores the
// total strictly decreasing paths.
int decrease = 0;
countPathsHelper(root, increase, decrease);
return { increase, decrease };
}
// Driver code
int main()
{
int N = 6;
TreeNode<int>* root
= new TreeNode<int>(N);
root->left = new TreeNode<int>(4);
root->right = new TreeNode<int>(7);
root->left->right = new TreeNode<int>(5);
root->right->left = new TreeNode<int>(6);
root->right->right = new TreeNode<int>(8);
// Function call
pair<int, int> ans = countPaths(root);
cout << ans.first << " " << ans.second;
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main {
static class Node {
int data;
Node left;
Node right;
Node(int data_value)
{
data = data_value;
this.left = null;
this.right = null;
}
}
// 'increase' stores the
// total strictly increasing paths.
static int increase;
// 'decrease' stores the
// total strictly decreasing paths.
static int decrease;
// Helper function to get the answer
static int[] countPathsHelper(Node root)
{
// If the root is NULL,
// then no strictly increasing or
// decreasing path.
if (root == null) {
int[] zero = {0,0};
return zero;
}
// Call the function for both
// the left and right child.
int[] p1
= countPathsHelper(root.left);
int[] p2
= countPathsHelper(root.right);
// Initialize 'inc' and 'dec' to 1
int inc = 1, dec = 1;
// If the left child is not NULL.
if (root.left != null) {
// Check if the value is
// increasing from parent to child.
if (root.data < root.left.data) {
// Add the count of strictly
// increasing paths of
// child to parent.
inc += p1[0];
}
// Check if the value is decreasing
// from parent to child.
if (root.data > root.left.data) {
// Add the count of strictly
// decreasing paths of
// child to parent.
dec += p1[1];
}
}
if (root.right != null) {
// Check if the value is
// increasing from parent to child.
if (root.data < root.right.data) {
// Add the count of strictly
// increasing paths of
// child to parent.
inc += p2[0];
}
// Check if the value is
// decreasing from parent to child
if (root.data > root.right.data) {
// Add the count of strictly
// decreasing paths of
// child to parent.
dec += p2[1];
}
}
// Add the total count of
// strictly increasing paths to
// the global strictly increasing
// paths counter.
increase += inc;
// Add the total count of
// strictly decreasing paths to
// the global strictly
// decreasing paths counter.
decrease += dec;
int[] ans = {inc,dec};
return ans;
}
// Function to count the paths
static int[] countPaths(Node root)
{
increase=0;
decrease=0;
countPathsHelper(root);
int[] ans = {increase,decrease};
return ans;
}
public static void main(String args[]) {
int N = 6;
Node root = new Node(N);
root.left = new Node(4);
root.right = new Node(7);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(8);
// Function call
int[] ans = countPaths(root);
System.out.println(ans[0] + " " + ans[1]);
}
}
// This code has been contributed by Sachin Sahara (sachin801)
Python3
# Python code for the above approach ## structure for a node class Node: def __init__(self, d): self.data = d self.left = None self.right = None ## 'increase' stores the ## total strictly increasing paths. increase = 0 ## 'decrease' stores the ## total strictly decreasing paths. decrease = 0 ## Helper function to get the answer def countPathsHelper(root): global increase global decrease ## If the root is NULL, ## then no strictly increasing or ## decreasing path. if (root == None): zero = [0, 0] return zero ## Call the function for both ## the left and right child. p1 = countPathsHelper(root.left) p2 = countPathsHelper(root.right) ## Initialize 'inc' and 'dec' to 1 inc = 1 dec = 1 ## If the left child is not NULL. if (root.left != None): ## Check if the value is ## increasing from parent to child. if (root.data < root.left.data): ## Add the count of strictly ## increasing paths of ## child to parent. inc += p1[0]; ## Check if the value is decreasing ## from parent to child. if (root.data > root.left.data): ## Add the count of strictly ## decreasing paths of ## child to parent. dec += p1[1] if (root.right != None): ## Check if the value is ## increasing from parent to child. if (root.data < root.right.data): ## Add the count of strictly ## increasing paths of ## child to parent. inc += p2[0] ## Check if the value is ## decreasing from parent to child if (root.data > root.right.data): ## Add the count of strictly ## decreasing paths of ## child to parent. dec += p2[1] ## Add the total count of ## strictly increasing paths to ## the global strictly increasing ## paths counter. increase += inc ## Add the total count of ## strictly decreasing paths to ## the global strictly ## decreasing paths counter. decrease += dec ans = [inc, dec] return ans ## Function to count the paths def countPaths(root): global increase global decrease increase = 0 decrease = 0 countPathsHelper(root) ans = [increase, decrease] return ans # Driver Code if __name__=='__main__': N = 6 root = Node(N) root.left = Node(4) root.right = Node(7) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(8) ## Function call ans = countPaths(root) print(ans[0], ans[1]) # This code is contributed by entertain2022.
C#
// C# program to count the number of
// strictly increasing and decreasing paths
using System;
public class GFG{
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data_value)
{
data = data_value;
this.left = null;
this.right = null;
}
}
// 'increase' stores the
// total strictly increasing paths.
static int increase;
// 'decrease' stores the
// total strictly decreasing paths.
static int decrease;
// Helper function to get the answer
static int[] countPathsHelper(Node root)
{
// If the root is NULL,
// then no strictly increasing or
// decreasing path.
if (root == null) {
int[] zero = {0,0};
return zero;
}
// Call the function for both
// the left and right child.
int[] p1 = countPathsHelper(root.left);
int[] p2 = countPathsHelper(root.right);
// Initialize 'inc' and 'dec' to 1
int inc = 1, dec = 1;
// If the left child is not NULL.
if (root.left != null) {
// Check if the value is
// increasing from parent to child.
if (root.data < root.left.data) {
// Add the count of strictly
// increasing paths of
// child to parent.
inc += p1[0];
}
// Check if the value is decreasing
// from parent to child.
if (root.data > root.left.data) {
// Add the count of strictly
// decreasing paths of
// child to parent.
dec += p1[1];
}
}
if (root.right != null) {
// Check if the value is
// increasing from parent to child.
if (root.data < root.right.data) {
// Add the count of strictly
// increasing paths of
// child to parent.
inc += p2[0];
}
// Check if the value is
// decreasing from parent to child
if (root.data > root.right.data) {
// Add the count of strictly
// decreasing paths of
// child to parent.
dec += p2[1];
}
}
// Add the total count of
// strictly increasing paths to
// the global strictly increasing
// paths counter.
increase += inc;
// Add the total count of
// strictly decreasing paths to
// the global strictly
// decreasing paths counter.
decrease += dec;
int[] ans = {inc,dec};
return ans;
}
// Function to count the paths
static int[] countPaths(Node root)
{
increase=0;
decrease=0;
countPathsHelper(root);
int[] ans = {increase,decrease};
return ans;
}
static public void Main (){
//Code
int N = 6;
Node root = new Node(N);
root.left = new Node(4);
root.right = new Node(7);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(8);
// Function call
int[] ans = countPaths(root);
Console.Write(ans[0] + " " + ans[1]);
}
}
// This code is contributed by shruti456rawal
Producción
10 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)