C++
// C++ program to print the longest leaf to leaf
// path
#include <bits/stdc++.h>
using namespace std;
// Tree node structure used in the program
struct Node {
int data;
Node *left, *right;
};
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Function to find height of a tree
int height(Node* root, int& ans, Node*(&k), int& lh, int& rh,
int& f)
{
if (root == NULL)
return 0;
int left_height = height(root->left, ans, k, lh, rh, f);
int right_height = height(root->right, ans, k, lh, rh, f);
// update the answer, because diameter of a
// tree is nothing but maximum value of
// (left_height + right_height + 1) for each node
if (ans < 1 + left_height + right_height) {
ans = 1 + left_height + right_height;
// save the root, this will help us finding the
// left and the right part of the diameter
k = root;
// save the height of left & right subtree as well.
lh = left_height;
rh = right_height;
}
return 1 + max(left_height, right_height);
}
// prints the root to leaf path
void printArray(int ints[], int len, int f)
{
int i;
// print left part of the path in reverse order
if (f == 0) {
for (i = len - 1; i >= 0; i--) {
printf("%d ", ints[i]);
}
}
// print right part of the path
else if (f == 1) {
for (i = 0; i < len; i++) {
printf("%d ", ints[i]);
}
}
}
// this function finds out all the root to leaf paths
void printPathsRecur(Node* node, int path[], int pathLen,
int max, int& f)
{
if (node == NULL)
return;
// append this node to the path array
path[pathLen] = node->data;
pathLen++;
// If it's a leaf, so print the path that led to here
if (node->left == NULL && node->right == NULL) {
// print only one path which is equal to the
// height of the tree.
if (pathLen == max && (f == 0 || f == 1)) {
printArray(path, pathLen, f);
f = 2;
}
}
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen, max, f);
printPathsRecur(node->right, path, pathLen, max, f);
}
}
// Computes the diameter of a binary tree with given root.
void diameter(Node* root)
{
if (root == NULL)
return;
// lh will store height of left subtree
// rh will store height of right subtree
int ans = INT_MIN, lh = 0, rh = 0;
// f is a flag whose value helps in printing
// left & right part of the diameter only once
int f = 0;
Node* k;
int height_of_tree = height(root, ans, k, lh, rh, f);
int lPath[100], pathlen = 0;
// print the left part of the diameter
printPathsRecur(k->left, lPath, pathlen, lh, f);
printf("%d ", k->data);
int rPath[100];
f = 1;
// print the right part of the diameter
printPathsRecur(k->right, rPath, pathlen, rh, f);
}
// Driver code
int main()
{
// Enter the binary tree ...
// 1
// / \
// 2 3
// / \
// 4 5
// \ / \
// 8 6 7
// /
// 9
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->left = newNode(6);
root->left->right->right = newNode(7);
root->left->left->right = newNode(8);
root->left->left->right->left = newNode(9);
diameter(root);
return 0;
}
Java
// Java program to print the longest leaf to leaf
// path
import java.io.*;
// Tree node structure used in the program
class Node
{
int data;
Node left, right;
Node(int val)
{
data = val;
left = right = null;
}
}
class GFG
{
static int ans, lh, rh, f;
static Node k;
public static Node Root;
// Function to find height of a tree
static int height(Node root)
{
if (root == null)
return 0;
int left_height = height(root.left);
int right_height = height(root.right);
// update the answer, because diameter of a
// tree is nothing but maximum value of
// (left_height + right_height + 1) for each node
if (ans < 1 + left_height + right_height)
{
ans = 1 + left_height + right_height;
// save the root, this will help us finding the
// left and the right part of the diameter
k = root;
// save the height of left & right subtree as well.
lh = left_height;
rh = right_height;
}
return 1 + Math.max(left_height, right_height);
}
// prints the root to leaf path
static void printArray(int[] ints, int len)
{
int i;
// print left part of the path in reverse order
if(f == 0)
{
for(i = len - 1; i >= 0; i--)
{
System.out.print(ints[i] + " ");
}
}
else if(f == 1)
{
for (i = 0; i < len; i++)
{
System.out.print(ints[i] + " ");
}
}
}
// this function finds out all the root to leaf paths
static void printPathsRecur(Node node, int[] path,
int pathLen, int max)
{
if (node == null)
return;
// append this node to the path array
path[pathLen] = node.data;
pathLen++;
// If it's a leaf, so print the path that led to here
if (node.left == null && node.right == null)
{
// print only one path which is equal to the
// height of the tree.
if (pathLen == max && (f == 0 || f == 1))
{
printArray(path, pathLen);
f = 2;
}
}
else
{
// otherwise try both subtrees
printPathsRecur(node.left, path, pathLen, max);
printPathsRecur(node.right, path, pathLen, max);
}
}
// Computes the diameter of a binary tree with given root.
static void diameter(Node root)
{
if (root == null)
return;
// lh will store height of left subtree
// rh will store height of right subtree
ans = Integer.MIN_VALUE;
lh = 0;
rh = 0;
// f is a flag whose value helps in printing
// left & right part of the diameter only once
f = 0;
int height_of_tree = height(root);
int[] lPath = new int[100];
int pathlen = 0;
// print the left part of the diameter
printPathsRecur(k.left, lPath, pathlen, lh);
System.out.print(k.data+" ");
int[] rPath = new int[100];
f = 1;
// print the right part of the diameter
printPathsRecur(k.right, rPath, pathlen, rh);
}
// Driver code
public static void main (String[] args)
{
// Enter the binary tree ...
// 1
// / \
// 2 3
// / \
// 4 5
// \ / \
// 8 6 7
// /
// 9
GFG.Root = new Node(1);
GFG.Root.left = new Node(2);
GFG.Root.right = new Node(3);
GFG.Root.left.left = new Node(4);
GFG.Root.left.right = new Node(5);
GFG.Root.left.right.left = new Node(6);
GFG.Root.left.right.right = new Node(7);
GFG.Root.left.left.right = new Node(8);
GFG.Root.left.left.right.left = new Node(9);
diameter(Root);
}
}
// This code is contributed by rag2127
Python3
# Python3 program to print the longest
# leaf to leaf path
# Tree node structure used in the program
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# Function to find height of a tree
def height(root):
global ans, k, lh, rh, f
if (root == None):
return 0
left_height = height(root.left)
right_height = height(root.right)
# Update the answer, because diameter of a
# tree is nothing but maximum value of
# (left_height + right_height + 1) for each node
if (ans < 1 + left_height + right_height):
ans = 1 + left_height + right_height
# Save the root, this will help us finding the
# left and the right part of the diameter
k = root
# Save the height of left & right
# subtree as well.
lh = left_height
rh = right_height
return 1 + max(left_height, right_height)
# Prints the root to leaf path
def printArray(ints, lenn, f):
# Print left part of the path
# in reverse order
if (f == 0):
for i in range(lenn - 1, -1, -1):
print(ints[i], end = " ")
# Print right part of the path
elif (f == 1):
for i in range(lenn):
print(ints[i], end = " ")
# This function finds out all the
# root to leaf paths
def printPathsRecur(node, path, maxm, pathlen):
global f
if (node == None):
return
# Append this node to the path array
path[pathlen] = node.data
pathlen += 1
# If it's a leaf, so print the
# path that led to here
if (node.left == None and node.right == None):
# Print only one path which is equal to the
# height of the tree.
# print(pathlen,"---",maxm)
if (pathlen == maxm and (f == 0 or f == 1)):
# print("innn")
printArray(path, pathlen,f)
f = 2
else:
# Otherwise try both subtrees
printPathsRecur(node.left, path, maxm, pathlen)
printPathsRecur(node.right, path, maxm, pathlen)
# Computes the diameter of a binary
# tree with given root.
def diameter(root):
global ans, lh, rh, f, k, pathLen
if (root == None):
return
# f is a flag whose value helps in printing
# left & right part of the diameter only once
height_of_tree = height(root)
lPath = [0 for i in range(100)]
# print(lh,"--",rh)
# Print the left part of the diameter
printPathsRecur(k.left, lPath, lh, 0);
print(k.data, end = " ")
rPath = [0 for i in range(100)]
f = 1
# Print the right part of the diameter
printPathsRecur(k.right, rPath, rh, 0)
# Driver code
if __name__ == '__main__':
k, lh, rh, f, ans, pathLen = None, 0, 0, 0, 0 - 10 ** 19, 0
# Enter the binary tree ...
# 1
# / \
# 2 3
# / \
# 4 5
# \ / \
# 8 6 7
# /
# 9
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(6)
root.left.right.right = Node(7)
root.left.left.right = Node(8)
root.left.left.right.left = Node(9)
diameter(root)
# This code is contributed by mohit kumar 29
C#
// C# program to print the longest leaf to leaf
// path
using System;
// Tree node structure used in the program
public class Node
{
public int data;
public Node left, right;
public Node(int val)
{
data = val;
left = right = null;
}
}
public class GFG
{
static int ans, lh, rh, f;
static Node k;
public static Node Root;
// Function to find height of a tree
static int height(Node root)
{
if (root == null)
return 0;
int left_height = height(root.left);
int right_height = height(root.right);
// update the answer, because diameter of a
// tree is nothing but maximum value of
// (left_height + right_height + 1) for each node
if (ans < 1 + left_height + right_height)
{
ans = 1 + left_height + right_height;
// save the root, this will help us finding the
// left and the right part of the diameter
k = root;
// save the height of left & right subtree as well.
lh = left_height;
rh = right_height;
}
return 1 + Math.Max(left_height, right_height);
}
// prints the root to leaf path
static void printArray(int[] ints, int len)
{
int i;
// print left part of the path in reverse order
if(f == 0)
{
for(i = len - 1; i >= 0; i--)
{
Console.Write(ints[i] + " ");
}
}
else if(f == 1)
{
for (i = 0; i < len; i++)
{
Console.Write(ints[i] + " ");
}
}
}
// this function finds out all the root to leaf paths
static void printPathsRecur(Node node, int[] path,int pathLen, int max)
{
if (node == null)
return;
// append this node to the path array
path[pathLen] = node.data;
pathLen++;
// If it's a leaf, so print the path that led to here
if (node.left == null && node.right == null)
{
// print only one path which is equal to the
// height of the tree.
if (pathLen == max && (f == 0 || f == 1))
{
printArray(path, pathLen);
f = 2;
}
}
else
{
// otherwise try both subtrees
printPathsRecur(node.left, path, pathLen, max);
printPathsRecur(node.right, path, pathLen, max);
}
}
// Computes the diameter of a binary tree with given root.
static void diameter(Node root)
{
if (root == null)
return;
// lh will store height of left subtree
// rh will store height of right subtree
ans = Int32.MinValue;
lh = 0;
rh = 0;
// f is a flag whose value helps in printing
// left & right part of the diameter only once
f = 0;
int height_of_tree= height(root);
int[] lPath = new int[100];
int pathlen = 0 * height_of_tree;
// print the left part of the diameter
printPathsRecur(k.left, lPath, pathlen, lh);
Console.Write(k.data+" ");
int[] rPath = new int[100];
f = 1;
// print the right part of the diameter
printPathsRecur(k.right, rPath, pathlen, rh);
}
// Driver code
static public void Main (){
// Enter the binary tree ...
// 1
// / \
// 2 3
// / \
// 4 5
// \ / \
// 8 6 7
// /
// 9
GFG.Root = new Node(1);
GFG.Root.left = new Node(2);
GFG.Root.right = new Node(3);
GFG.Root.left.left = new Node(4);
GFG.Root.left.right = new Node(5);
GFG.Root.left.right.left = new Node(6);
GFG.Root.left.right.right = new Node(7);
GFG.Root.left.left.right = new Node(8);
GFG.Root.left.left.right.left = new Node(9);
diameter(Root);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program to print the longest leaf to leaf
// path
// Tree node structure used in the program
class Node
{
constructor(val)
{
this.data=val;
this.left = this.right = null;
}
}
let ans, lh, rh, f;
let k;
let Root;
// Function to find height of a tree
function height(root)
{
if (root == null)
return 0;
let left_height = height(root.left);
let right_height = height(root.right);
// update the answer, because diameter of a
// tree is nothing but maximum value of
// (left_height + right_height + 1) for each node
if (ans < 1 + left_height + right_height)
{
ans = 1 + left_height + right_height;
// save the root, this will help us finding the
// left and the right part of the diameter
k = root;
// save the height of left & right subtree as well.
lh = left_height;
rh = right_height;
}
return 1 + Math.max(left_height, right_height);
}
// prints the root to leaf path
function printArray(ints,len)
{
let i;
// print left part of the path in reverse order
if(f == 0)
{
for(i = len - 1; i >= 0; i--)
{
document.write(ints[i] + " ");
}
}
else if(f == 1)
{
for (i = 0; i < len; i++)
{
document.write(ints[i] + " ");
}
}
}
// this function finds out all the root to leaf paths
function printPathsRecur(node,path,pathLen,max)
{
if (node == null)
return;
// append this node to the path array
path[pathLen] = node.data;
pathLen++;
// If it's a leaf, so print the path that led to here
if (node.left == null && node.right == null)
{
// print only one path which is equal to the
// height of the tree.
if (pathLen == max && (f == 0 || f == 1))
{
printArray(path, pathLen);
f = 2;
}
}
else
{
// otherwise try both subtrees
printPathsRecur(node.left, path, pathLen, max);
printPathsRecur(node.right, path, pathLen, max);
}
}
// Computes the diameter of a binary tree with given root.
function diameter(root)
{
if (root == null)
return;
// lh will store height of left subtree
// rh will store height of right subtree
ans = Number.MIN_VALUE;
lh = 0;
rh = 0;
// f is a flag whose value helps in printing
// left & right part of the diameter only once
f = 0;
let height_of_tree = height(root);
let lPath = new Array(100);
let pathlen = 0;
// print the left part of the diameter
printPathsRecur(k.left, lPath, pathlen, lh);
document.write(k.data+" ");
let rPath = new Array(100);
f = 1;
// print the right part of the diameter
printPathsRecur(k.right, rPath, pathlen, rh);
}
// Driver code
// Enter the binary tree ...
// 1
// / \
// 2 3
// / \
// 4 5
// \ / \
// 8 6 7
// /
// 9
Root = new Node(1);
Root.left = new Node(2);
Root.right = new Node(3);
Root.left.left = new Node(4);
Root.left.right = new Node(5);
Root.left.right.left = new Node(6);
Root.left.right.right = new Node(7);
Root.left.left.right = new Node(8);
Root.left.left.right.left = new Node(9);
diameter(Root);
// This code is contributed by patel2127
</script>
Complejidad temporal: O(n) donde n es el tamaño del árbol binario
Espacio auxiliar: O(h) donde h es la altura del árbol binario.
Publicación traducida automáticamente
Artículo escrito por Rajesh_Sethi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA