Dado un árbol binario, encuentre la longitud de la ruta más larga que se compone de Nodes con valores consecutivos en orden creciente. Cada Node se considera como un camino de longitud 1.
Ejemplos:
C++
// C++ Program to find Maximum Consecutive
// Path Length in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// To represent a node of a Binary Tree
struct Node
{
Node *left, *right;
int val;
};
// Create a new Node and return its address
Node *newNode(int val)
{
Node *temp = new Node();
temp->val = val;
temp->left = temp->right = NULL;
return temp;
}
// Returns the maximum consecutive Path Length
int maxPathLenUtil(Node *root, int prev_val, int prev_len)
{
if (!root)
return prev_len;
// Get the value of Current Node
// The value of the current node will be
// prev Node for its left and right children
int cur_val = root->val;
// If current node has to be a part of the
// consecutive path then it should be 1 greater
// than the value of the previous node
if (cur_val == prev_val+1)
{
// a) Find the length of the Left Path
// b) Find the length of the Right Path
// Return the maximum of Left path and Right path
return max(maxPathLenUtil(root->left, cur_val, prev_len+1),
maxPathLenUtil(root->right, cur_val, prev_len+1));
}
// Find length of the maximum path under subtree rooted with this
// node (The path may or may not include this node)
int newPathLen = max(maxPathLenUtil(root->left, cur_val, 1),
maxPathLenUtil(root->right, cur_val, 1));
// Take the maximum previous path and path under subtree rooted
// with this node.
return max(prev_len, newPathLen);
}
// A wrapper over maxPathLenUtil().
int maxConsecutivePathLength(Node *root)
{
// Return 0 if root is NULL
if (root == NULL)
return 0;
// Else compute Maximum Consecutive Increasing Path
// Length using maxPathLenUtil.
return maxPathLenUtil(root, root->val-1, 0);
}
//Driver program to test above function
int main()
{
Node *root = newNode(10);
root->left = newNode(11);
root->right = newNode(9);
root->left->left = newNode(13);
root->left->right = newNode(12);
root->right->left = newNode(13);
root->right->right = newNode(8);
cout << "Maximum Consecutive Increasing Path Length is "
<< maxConsecutivePathLength(root);
return 0;
}
Java
// Java Program to find Maximum Consecutive
// Path Length in a Binary Tree
import java.util.*;
class GfG {
// To represent a node of a Binary Tree
static class Node
{
Node left, right;
int val;
}
// Create a new Node and return its address
static Node newNode(int val)
{
Node temp = new Node();
temp.val = val;
temp.left = null;
temp.right = null;
return temp;
}
// Returns the maximum consecutive Path Length
static int maxPathLenUtil(Node root, int prev_val, int prev_len)
{
if (root == null)
return prev_len;
// Get the value of Current Node
// The value of the current node will be
// prev Node for its left and right children
int cur_val = root.val;
// If current node has to be a part of the
// consecutive path then it should be 1 greater
// than the value of the previous node
if (cur_val == prev_val+1)
{
// a) Find the length of the Left Path
// b) Find the length of the Right Path
// Return the maximum of Left path and Right path
return Math.max(maxPathLenUtil(root.left, cur_val, prev_len+1),
maxPathLenUtil(root.right, cur_val, prev_len+1));
}
// Find length of the maximum path under subtree rooted with this
// node (The path may or may not include this node)
int newPathLen = Math.max(maxPathLenUtil(root.left, cur_val, 1),
maxPathLenUtil(root.right, cur_val, 1));
// Take the maximum previous path and path under subtree rooted
// with this node.
return Math.max(prev_len, newPathLen);
}
// A wrapper over maxPathLenUtil().
static int maxConsecutivePathLength(Node root)
{
// Return 0 if root is NULL
if (root == null)
return 0;
// Else compute Maximum Consecutive Increasing Path
// Length using maxPathLenUtil.
return maxPathLenUtil(root, root.val-1, 0);
}
//Driver program to test above function
public static void main(String[] args)
{
Node root = newNode(10);
root.left = newNode(11);
root.right = newNode(9);
root.left.left = newNode(13);
root.left.right = newNode(12);
root.right.left = newNode(13);
root.right.right = newNode(8);
System.out.println("Maximum Consecutive Increasing Path Length is "+maxConsecutivePathLength(root));
}
}
Python3
# Python program to find Maximum consecutive
# path length in binary tree
# A binary tree node
class Node:
# Constructor to create a new node
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Returns the maximum consecutive path length
def maxPathLenUtil(root, prev_val, prev_len):
if root is None:
return prev_len
# Get the value of current node
# The value of the current node will be
# prev node for its left and right children
curr_val = root.val
# If current node has to be a part of the
# consecutive path then it should be 1 greater
# than the value of the previous node
if curr_val == prev_val +1 :
# a) Find the length of the left path
# b) Find the length of the right path
# Return the maximum of left path and right path
return max(maxPathLenUtil(root.left, curr_val, prev_len+1),
maxPathLenUtil(root.right, curr_val, prev_len+1))
# Find the length of the maximum path under subtree
# rooted with this node
newPathLen = max(maxPathLenUtil(root.left, curr_val, 1),
maxPathLenUtil(root.right, curr_val, 1))
# Take the maximum previous path and path under subtree
# rooted with this node
return max(prev_len , newPathLen)
# A Wrapper over maxPathLenUtil()
def maxConsecutivePathLength(root):
# Return 0 if root is None
if root is None:
return 0
# Else compute maximum consecutive increasing path
# length using maxPathLenUtil
return maxPathLenUtil(root, root.val -1 , 0)
# Driver program to test above function
root = Node(10)
root.left = Node(11)
root.right = Node(9)
root.left.left = Node(13)
root.left.right = Node(12)
root.right.left = Node(13)
root.right.right = Node(8)
print ("Maximum Consecutive Increasing Path Length is",)
print (maxConsecutivePathLength(root))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# Program to find Maximum Consecutive
// Path Length in a Binary Tree
using System;
class GfG
{
// To represent a node of a Binary Tree
class Node
{
public Node left, right;
public int val;
}
// Create a new Node and return its address
static Node newNode(int val)
{
Node temp = new Node();
temp.val = val;
temp.left = null;
temp.right = null;
return temp;
}
// Returns the maximum consecutive Path Length
static int maxPathLenUtil(Node root,
int prev_val, int prev_len)
{
if (root == null)
return prev_len;
// Get the value of Current Node
// The value of the current node will be
// prev Node for its left and right children
int cur_val = root.val;
// If current node has to be a part of the
// consecutive path then it should be 1 greater
// than the value of the previous node
if (cur_val == prev_val+1)
{
// a) Find the length of the Left Path
// b) Find the length of the Right Path
// Return the maximum of Left path and Right path
return Math.Max(maxPathLenUtil(root.left, cur_val, prev_len+1),
maxPathLenUtil(root.right, cur_val, prev_len+1));
}
// Find length of the maximum path under subtree rooted with this
// node (The path may or may not include this node)
int newPathLen = Math.Max(maxPathLenUtil(root.left, cur_val, 1),
maxPathLenUtil(root.right, cur_val, 1));
// Take the maximum previous path and path under subtree rooted
// with this node.
return Math.Max(prev_len, newPathLen);
}
// A wrapper over maxPathLenUtil().
static int maxConsecutivePathLength(Node root)
{
// Return 0 if root is NULL
if (root == null)
return 0;
// Else compute Maximum Consecutive Increasing Path
// Length using maxPathLenUtil.
return maxPathLenUtil(root, root.val - 1, 0);
}
// Driver code
public static void Main(String[] args)
{
Node root = newNode(10);
root.left = newNode(11);
root.right = newNode(9);
root.left.left = newNode(13);
root.left.right = newNode(12);
root.right.left = newNode(13);
root.right.right = newNode(8);
Console.WriteLine("Maximum Consecutive" +
" Increasing Path Length is "+
maxConsecutivePathLength(root));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to find Maximum Consecutive
// Path Length in a Binary Tree
// To represent a node of a Binary Tree
class Node
{
constructor(val)
{
this.val = val;
this.left = this.right = null;
}
}
// Returns the maximum consecutive Path Length
function maxPathLenUtil(root,prev_val,prev_len)
{
if (root == null)
return prev_len;
// Get the value of Current Node
// The value of the current node will be
// prev Node for its left and right children
let cur_val = root.val;
// If current node has to be a part of the
// consecutive path then it should be 1 greater
// than the value of the previous node
if (cur_val == prev_val+1)
{
// a) Find the length of the Left Path
// b) Find the length of the Right Path
// Return the maximum of Left path and Right path
return Math.max(maxPathLenUtil(root.left, cur_val, prev_len+1),
maxPathLenUtil(root.right, cur_val, prev_len+1));
}
// Find length of the maximum path under subtree rooted with this
// node (The path may or may not include this node)
let newPathLen = Math.max(maxPathLenUtil(root.left, cur_val, 1),
maxPathLenUtil(root.right, cur_val, 1));
// Take the maximum previous path and path under subtree rooted
// with this node.
return Math.max(prev_len, newPathLen);
}
// A wrapper over maxPathLenUtil().
function maxConsecutivePathLength(root)
{
// Return 0 if root is NULL
if (root == null)
return 0;
// Else compute Maximum Consecutive Increasing Path
// Length using maxPathLenUtil.
return maxPathLenUtil(root, root.val-1, 0);
}
// Driver program to test above function
let root = new Node(10);
root.left = new Node(11);
root.right = new Node(9);
root.left.left = new Node(13);
root.left.right = new Node(12);
root.right.left = new Node(13);
root.right.right = new Node(8);
document.write("Maximum Consecutive Increasing Path Length is "+
maxConsecutivePathLength(root)+"<br>");
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA