原文:
给定一个二叉树，任务是打印从根节点到叶节点的最长路径。如果有多个答案，打印其中任何一个。
示例:
input:
4
/ \
3 6
/ \
5 7
output:
4 -> 6 -> 7
explanation:
longest paths from root to leaf
are (4 -> 6 -> 5)
and (4 -> 6 -> 7).
print any of them.
input:
1
/ \
2 3
/ \
4 5
\
6
output:
1 -> 2 -> 5 -> 6
天真方法:思路是生成从根节点到所有叶节点的所有可能路径，跟踪最大长度的路径，最后打印最长路径。
时间复杂度: o(n 2 )
高效途径:思路是利用高效解决这个问题。主要思想是递归地从左子树和右子树中获得最长的路径，然后将当前节点添加到一个更长的节点，这将是从当前节点到叶子的最长路径。从根节点开始，对递归调用的每个节点执行以下步骤。
- 如果根节点为空，则不存在路径，返回一个空向量。
- 通过递归遍历根- >右，得到向量右向量中右子树的最长路径。
- 类似地，通过递归遍历左根- >来获得向量左向量中从左子树开始的最长路径。
- 比较右向量和左向量的长度，并将当前节点附加到两个向量中较长的一个上并返回该向量。
通过遵循上述步骤，在树遍历结束时获得的向量是可能的最长路径。反向打印矢量，作为从根到叶的最长路径。
请看这张图片，了解如何使用从左和右子树的节点开始的最长路径来获得从当前节点开始的最长路径:
下面是上述方法的实现:
c
// c program to print longest path
// from root to leaf in a binary tree
#include
using namespace std;
// tree node structure
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 and return the
// longest path
vector longestpath(node* root)
{
// if root is null means there
// is no binary tree so
// return a empty vector
if (root == null) {
vector temp
= {};
return temp;
}
// recursive call on root->right
vector rightvect
= longestpath(root->right);
// recursive call on root->left
vector leftvect
= longestpath(root->left);
// compare the size of the two vectors
// and insert current node accordingly
if (leftvect.size() > rightvect.size())
leftvect.push_back(root->data);
else
rightvect.push_back(root->data);
// return the appropriate vector
return (leftvect.size() > rightvect.size()
? leftvect
: rightvect);
}
// driver code
int main()
{
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->right = newnode(6);
vector output = longestpath(root);
int n = output.size();
cout << output[n - 1];
for (int i = n - 2; i >= 0; i--) {
cout << " -> " << output[i];
}
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print longest path
// from root to leaf in a binary tree
import java.io.*;
import java.util.arraylist;
class gfg{
// binary tree node
static class node
{
node left;
node right;
int data;
};
// function to create a new
// binary node
static node newnode(int data)
{
node temp = new node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// function to find and return the
// longest path
public static arraylist longestpath(node root)
{
// if root is null means there
// is no binary tree so
// return a empty vector
if(root == null)
{
arraylist output = new arraylist<>();
return output;
}
// recursive call on root.right
arraylist right = longestpath(root.right);
// recursive call on root.left
arraylist left = longestpath(root.left);
// compare the size of the two arraylist
// and insert current node accordingly
if(right.size() < left.size())
{
left.add(root.data);
}
else
{
right.add(root.data);
}
// return the appropriate arraylist
return (left.size() >
right.size() ? left :right);
}
// driver code
public static void main(string[] args)
{
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.right = newnode(6);
arraylist output = longestpath(root);
int n = output.size();
system.out.print(output.get(n - 1));
for(int i = n - 2; i >= 0; i--)
{
system.out.print(" -> " output.get(i));
}
}
}
// this code is contributed by hamreetsingh
python 3
# python3 program to print longest path
# from root to leaf in a binary tree
# tree node structure
class node:
def __init__(self, key):
self.data = key
self.left = none
self.right = none
# function to find and return the
# longest path
def longestpath(root):
# if root is null means there
# is no binary tree so
# return a empty vector
if (root == none):
return []
# recursive call on root.right
rightvect = longestpath(root.right)
# recursive call on root.left
leftvect = longestpath(root.left)
# compare the size of the two vectors
# and insert current node accordingly
if (len(leftvect) > len(rightvect)):
leftvect.append(root.data)
else:
rightvect.append(root.data)
# return the appropriate vector
if len(leftvect) > len(rightvect):
return leftvect
return rightvect
# driver code
if __name__ == '__main__':
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(5)
root.left.right.right = node(6)
output = longestpath(root)
n = len(output)
print(output[n - 1], end = "")
for i in range(n - 2, -1, -1):
print(" ->", output[i], end = "")
# this code is contributed by mohit kumar 29
c
// c# program to print
// longest path from
// root to leaf in a
// binary tree
using system;
using system.collections.generic;
class gfg{
// binary tree node
class node
{
public node left;
public node right;
public int data;
};
// function to create a new
// binary node
static node newnode(int data)
{
node temp = new node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// function to find and
// return the longest path
static list longestpath(node root)
{
// if root is null means there
// is no binary tree so
// return a empty vector
if(root == null)
{
list output = new list();
return output;
}
// recursive call on root.right
list right = longestpath(root.right);
// recursive call on root.left
list left = longestpath(root.left);
// compare the size of the two list
// and insert current node accordingly
if(right.count < left.count)
{
left.add(root.data);
}
else
{
right.add(root.data);
}
// return the appropriate list
return (left.count >
right.count ?
left :right);
}
// driver code
public static void main(string[] args)
{
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.right = newnode(6);
list output = longestpath(root);
int n = output.count;
console.write(output[n - 1]);
for(int i = n - 2; i >= 0; i--)
{
console.write(" -> " output[i]);
}
}
}
// this code is contributed by 29ajaykumar
java 描述语言
output
1 -> 2 -> 5 -> 6
时间复杂度:o(n) t5辅助空间:** o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
