Dado un árbol binario, encuentre la longitud del camino que tiene el número máximo de curvas.
Nota: Aquí, doblar indica cambiar de izquierda a derecha o viceversa mientras se atraviesa el árbol.
Por ejemplo, considere las siguientes rutas (L significa moverse hacia la izquierda, R significa moverse hacia la derecha):
LLRRRR: 1 curva
RLLLRR: 2 curvas
LRLRLR: 5 curvas
Requisito previo: encontrar la longitud máxima de la ruta en un árbol binario
Ejemplos:
Input :
4
/ \
2 6
/ \ / \
1 3 5 7
/
9
/ \
12 10
\
11
/ \
45 13
\
14
Output : 6
In the above example, the path 4-> 6-> 7-> 9-> 10-> 11-> 45
is having the maximum number of bends, i.e., 3.
The length of this path is 6.
Enfoque:
La idea es atravesar el árbol para los subárboles izquierdo y derecho de la raíz. Mientras se desplaza, mantenga un registro de la dirección del movimiento (izquierda o derecha). Siempre que la dirección del movimiento cambie de izquierda a derecha o viceversa, incremente el número de curvas en la ruta actual en 1.
Al llegar al Node hoja, compare la cantidad de curvas en la ruta actual con la cantidad máxima de curvas (es decir, maxBends ) visto hasta ahora en un camino de raíz a hoja. Si la cantidad de curvas en la ruta actual es mayor que maxBends, actualice maxBends igual a la cantidad de curvas en la ruta actual y actualice la longitud máxima de la ruta (es decir, len) también a la longitud de la ruta actual.
Implementación:
C++
// C++ program to find path length
// having maximum number of bends
#include <bits/stdc++.h>
using namespace std;
// structure node
struct Node {
int key;
struct Node* left;
struct Node* right;
};
// Utility function to create a new node
struct Node* newNode(int key)
{
struct Node* node = new Node();
node->left = NULL;
node->right = NULL;
node->key = key;
return node;
}
/* Recursive function to calculate the path
length having maximum number of bends.
The following are parameters for this function.
node --> pointer to the current node
dir --> determines whether the current node
is left or right child of it's parent node
bends --> number of bends so far in the
current path.
maxBends --> maximum number of bends in a
path from root to leaf
soFar --> length of the current path so
far traversed
len --> length of the path having maximum
number of bends
*/
void findMaxBendsUtil(struct Node* node,
char dir, int bends,
int* maxBends, int soFar,
int* len)
{
// Base Case
if (node == NULL)
return;
// Leaf node
if (node->left == NULL && node->right == NULL) {
if (bends > *maxBends) {
*maxBends = bends;
*len = soFar;
}
}
// Recurring for both left and right child
else {
if (dir == 'l') {
findMaxBendsUtil(node->left, dir,
bends, maxBends,
soFar + 1, len);
findMaxBendsUtil(node->right, 'r',
bends + 1, maxBends,
soFar + 1, len);
}
else {
findMaxBendsUtil(node->right, dir,
bends, maxBends,
soFar + 1, len);
findMaxBendsUtil(node->left, 'l',
bends + 1, maxBends,
soFar + 1, len);
}
}
}
// Helper function to call findMaxBendsUtil()
int findMaxBends(struct Node* node)
{
if (node == NULL)
return 0;
int len = 0, bends = 0, maxBends = -1;
// Call for left subtree of the root
if (node->left)
findMaxBendsUtil(node->left, 'l',
bends, &maxBends, 1, &len);
// Call for right subtree of the root
if (node->right)
findMaxBendsUtil(node->right, 'r', bends,
&maxBends, 1, &len);
// Include the root node as well in the path length
len++;
return len;
}
// Driver code
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
\
1
/
9
*/
struct Node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(2);
root->right->left->right = newNode(1);
root->right->left->right->left = newNode(9);
cout << findMaxBends(root) - 1;
return 0;
}
Java
// Java program to find path length
// having maximum number of bends
import java.util.*;
class GFG
{
// structure node
static class Node
{
int key;
Node left;
Node right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = null;
node.right = null;
node.key = key;
return node;
}
/* Recursive function to calculate the path
length having maximum number of bends.
The following are parameters for this function.
node -. pointer to the current node
dir -. determines whether the current node
is left or right child of it's parent node
bends -. number of bends so far in the
current path.
maxBends -. maximum number of bends in a
path from root to leaf
soFar -. length of the current path so
far traversed
len -. length of the path having maximum
number of bends
*/
static int maxBends;
static int len;
private static final char LEFT = 'l';
private static final char RIGHT = 'r';
static void findMaxBendsUtil(Node node,
char dir, int bends,
int lenSoFar)
{
// Base Case
if (node == null)
return;
// Leaf node
if (node.left == null && node.right == null)
{
if (bends > maxBends)
{
maxBends = bends;
len = lenSoFar;
}
}
// Recurring for both left and right child
else
{
if (dir == LEFT)
{
findMaxBendsUtil(node.left, dir,
bends,
lenSoFar + 1);
findMaxBendsUtil(node.right, RIGHT,
bends + 1,
lenSoFar + 1);
}
else
{
findMaxBendsUtil(node.right, dir,
bends,
lenSoFar + 1);
findMaxBendsUtil(node.left, LEFT,
bends + 1,
lenSoFar + 1);
}
}
}
// Helper function to call findMaxBendsUtil()
static int findMaxBends(Node node)
{
if (node == null)
return 0;
len = 0;
maxBends = -1;
int bends = 0;
// Call for left subtree of the root
if (node.left != null)
findMaxBendsUtil(node.left, LEFT,
bends, 1);
// Call for right subtree of the root
if (node.right != null)
findMaxBendsUtil(node.right, RIGHT, bends,
1);
// Include the root node as well in the path length
len++;
return len;
}
// Driver code
public static void main(String[] args)
{
/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
\
1
/
9
*/
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.left = newNode(2);
root.right.left.right = newNode(1);
root.right.left.right.left = newNode(9);
System.out.print(findMaxBends(root) - 1);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find path Length # having maximum number of bends # Utility function to create a new node class newNode: def __init__(self, key): self.left = None self.right = None self.key = key # Recursive function to calculate the path # Length having maximum number of bends. # The following are parameters for this function. # node -. pointer to the current node # Dir -. determines whether the current node # is left or right child of it's parent node # bends -. number of bends so far in the # current path. # maxBends -. maximum number of bends in a # path from root to leaf # soFar -. Length of the current path so # far traversed # Len -. Length of the path having maximum # number of bends def findMaxBendsUtil(node, Dir, bends, maxBends, soFar, Len): # Base Case if (node == None): return # Leaf node if (node.left == None and node.right == None): if (bends > maxBends[0]): maxBends[0] = bends Len[0] = soFar # Having both left and right child else: if (Dir == 'l'): findMaxBendsUtil(node.left, Dir, bends, maxBends, soFar + 1, Len) findMaxBendsUtil(node.right, 'r', bends + 1, maxBends, soFar + 1, Len) else: findMaxBendsUtil(node.right, Dir, bends, maxBends, soFar + 1, Len) findMaxBendsUtil(node.left, 'l', bends + 1, maxBends, soFar + 1, Len) # Helper function to call findMaxBendsUtil() def findMaxBends(node): if (node == None): return 0 Len = [0] bends = 0 maxBends = [-1] # Call for left subtree of the root if (node.left): findMaxBendsUtil(node.left, 'l', bends, maxBends, 1, Len) # Call for right subtree of the root if (node.right): findMaxBendsUtil(node.right, 'r', bends, maxBends, 1, Len) # Include the root node as well # in the path Length Len[0] += 1 return Len[0] # Driver code if __name__ == '__main__': # Constructed binary tree is # 10 # / \ # 8 2 # / \ / # 3 5 2 # \ # 1 # / # 9 root = newNode(10) root.left = newNode(8) root.right = newNode(2) root.left.left = newNode(3) root.left.right = newNode(5) root.right.left = newNode(2) root.right.left.right = newNode(1) root.right.left.right.left = newNode(9) print(findMaxBends(root) - 1) # This code is contributed by PranchalK
C#
// C# program to find path length
// having maximum number of bends
using System;
public class GFG
{
// structure node
public
class Node
{
public
int key;
public
Node left;
public
Node right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = null;
node.right = null;
node.key = key;
return node;
}
/* Recursive function to calculate the path
length having maximum number of bends.
The following are parameters for this function.
node -. pointer to the current node
dir -. determines whether the current node
is left or right child of it's parent node
bends -. number of bends so far in the
current path.
maxBends -. maximum number of bends in a
path from root to leaf
soFar -. length of the current path so
far traversed
len -. length of the path having maximum
number of bends
*/
static int maxBends;
static int len;
static void findMaxBendsUtil(Node node,
char dir, int bends,
int soFar)
{
// Base Case
if (node == null)
return;
// Leaf node
if (node.left == null && node.right == null)
{
if (bends > maxBends)
{
maxBends = bends;
len = soFar;
}
}
// Recurring for both left and right child
else
{
if (dir == 'l')
{
findMaxBendsUtil(node.left, dir,
bends,
soFar + 1);
findMaxBendsUtil(node.right, 'r',
bends + 1,
soFar + 1);
}
else
{
findMaxBendsUtil(node.right, dir,
bends,
soFar + 1);
findMaxBendsUtil(node.left, 'l',
bends + 1,
soFar + 1);
}
}
}
// Helper function to call findMaxBendsUtil()
static int findMaxBends(Node node)
{
if (node == null)
return 0;
len = 0;
maxBends = -1;
int bends = 0;
// Call for left subtree of the root
if (node.left != null)
findMaxBendsUtil(node.left, 'l',
bends, 1);
// Call for right subtree of the root
if (node.right != null)
findMaxBendsUtil(node.right, 'r', bends,
1);
// Include the root node as well in the path length
len++;
return len;
}
// Driver code
public static void Main(String[] args)
{
/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
\
1
/
9
*/
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.left = newNode(2);
root.right.left.right = newNode(1);
root.right.left.right.left = newNode(9);
Console.Write(findMaxBends(root) - 1);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find path length
// having maximum number of bends
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Utility function to create a new node
function newNode(key)
{
let node = new Node(key);
return node;
}
/* Recursive function to calculate the path
length having maximum number of bends.
The following are parameters for this function.
node -. pointer to the current node
dir -. determines whether the current node
is left or right child of it's parent node
bends -. number of bends so far in the
current path.
maxBends -. maximum number of bends in a
path from root to leaf
soFar -. length of the current path so
far traversed
len -. length of the path having maximum
number of bends
*/
let maxBends;
let len;
function findMaxBendsUtil(node, dir, bends, soFar)
{
// Base Case
if (node == null)
return;
// Leaf node
if (node.left == null && node.right == null)
{
if (bends > maxBends)
{
maxBends = bends;
len = soFar;
}
}
// Recurring for both left and right child
else
{
if (dir == 'l')
{
findMaxBendsUtil(node.left, dir,
bends,
soFar + 1);
findMaxBendsUtil(node.right, 'r',
bends + 1,
soFar + 1);
}
else
{
findMaxBendsUtil(node.right, dir,
bends,
soFar + 1);
findMaxBendsUtil(node.left, 'l',
bends + 1,
soFar + 1);
}
}
}
// Helper function to call findMaxBendsUtil()
function findMaxBends(node)
{
if (node == null)
return 0;
len = 0;
maxBends = -1;
let bends = 0;
// Call for left subtree of the root
if (node.left != null)
findMaxBendsUtil(node.left, 'l',
bends, 1);
// Call for right subtree of the root
if (node.right != null)
findMaxBendsUtil(node.right, 'r', bends,
1);
// Include the root node as well in the path length
len++;
return len;
}
/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
\
1
/
9
*/
let root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.left = newNode(2);
root.right.left.right = newNode(1);
root.right.left.right.left = newNode(9);
document.write(findMaxBends(root) - 1);
</script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por Ashish Jindal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA