原文:
给定具有不同节点的二叉树(没有两个节点具有相同的数据值)。问题是打印从根到给定节点 x 的路径。如果节点 x 不存在，则打印“无路径”。
示例:
input : 1
/ \
2 3
/ \ / \
4 5 6 7
x = 5
output : 1->2->5
方法:创建一个递归函数，遍历二叉树中的不同路径，找到需要的节点 x 。如果节点 x 存在，则它返回真，并在某个数组arr【】中累积路径节点。否则返回假。 以下是遍历过程中的情况:
- 如果根=空，返回假。
- 将根的数据推入 arr[] 。
- 如果根的数据= x ，返回真。
- 如果节点 x 出现在根的左或右子树中，返回 true。
- 否则从 arr[] 中移除根的数据值，并返回 false。
可以从其他函数访问该递归函数，以检查节点 x 是否存在，如果存在，则可以从 arr[] 访问路径节点。您可以全局定义 arr[] 或将它的引用传递给递归函数。
c
// c implementation to print the path from root
// to a given node in a binary tree
#include
using namespace std;
// structure of a node of binary tree
struct node
{
int data;
node *left, *right;
};
/* helper function that allocates a new node with the
given data and null left and right pointers. */
struct node* getnode(int data)
{
struct node *newnode = new node;
newnode->data = data;
newnode->left = newnode->right = null;
return newnode;
}
// returns true if there is a path from root
// to the given node. it also populates
// 'arr' with the given path
bool haspath(node *root, vector& arr, int x)
{
// if root is null
// there is no path
if (!root)
return false;
// push the node's value in 'arr'
arr.push_back(root->data);
// if it is the required node
// return true
if (root->data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (haspath(root->left, arr, x) ||
haspath(root->right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// thus, remove current node's value from
// 'arr'and then return false
arr.pop_back();
return false;
}
// function to print the path from root to the
// given node if the node lies in the binary tree
void printpath(node *root, int x)
{
// vector to store the path
vector arr;
// if required node 'x' is present
// then print the path
if (haspath(root, arr, x))
{
for (int i=0; i";
cout << arr[arr.size() - 1];
}
// 'x' is not present in the binary tree
else
cout << "no path";
}
// driver program to test above
int main()
{
// binary tree formation
struct node *root = getnode(1);
root->left = getnode(2);
root->right = getnode(3);
root->left->left = getnode(4);
root->left->right = getnode(5);
root->right->left = getnode(6);
root->right->right = getnode(7);
int x = 5;
printpath(root, x);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print the path from root
// to a given node in a binary tree
import java.util.arraylist;
public class printpath {
// returns true if there is a path from root
// to the given node. it also populates
// 'arr' with the given path
public static boolean haspath(node root, arraylist arr, int x)
{
// if root is null
// there is no path
if (root==null)
return false;
// push the node's value in 'arr'
arr.add(root.data);
// if it is the required node
// return true
if (root.data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (haspath(root.left, arr, x) ||
haspath(root.right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// thus, remove current node's value from
// 'arr'and then return false
arr.remove(arr.size()-1);
return false;
}
// function to print the path from root to the
// given node if the node lies in the binary tree
public static void printpath(node root, int x)
{
// arraylist to store the path
arraylist arr=new arraylist<>();
// if required node 'x' is present
// then print the path
if (haspath(root, arr, x))
{
for (int i=0; i");
system.out.print(arr.get(arr.size() - 1));
}
// 'x' is not present in the binary tree
else
system.out.print("no path");
}
public static void main(string args[]) {
node 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.right.left = new node(6);
root.right.right = new node(7);
int x=5;
printpath(root, x);
}
}
// a node of binary tree
class node
{
int data;
node left, right;
node(int data)
{
this.data=data;
left=right=null;
}
};
//this code is contributed by gaurav tiwari
python 3
# python3 implementation to print the path from
# root to a given node in a binary tree
# helper class that allocates a new node
# with the given data and none left and
# right pointers.
class getnode:
def __init__(self, data):
self.data = data
self.left = self.right = none
# returns true if there is a path from
# root to the given node. it also
# populates 'arr' with the given path
def haspath(root, arr, x):
# if root is none there is no path
if (not root):
return false
# push the node's value in 'arr'
arr.append(root.data)
# if it is the required node
# return true
if (root.data == x):
return true
# else check whether the required node
# lies in the left subtree or right
# subtree of the current node
if (haspath(root.left, arr, x) or
haspath(root.right, arr, x)):
return true
# required node does not lie either in
# the left or right subtree of the current
# node. thus, remove current node's value
# from 'arr'and then return false
arr.pop(-1)
return false
# function to print the path from root to
# the given node if the node lies in
# the binary tree
def printpath(root, x):
# vector to store the path
arr = []
# if required node 'x' is present
# then print the path
if (haspath(root, arr, x)):
for i in range(len(arr) - 1):
print(arr[i], end = "->")
print(arr[len(arr) - 1])
# 'x' is not present in the
# binary tree
else:
print("no path")
# driver code
if __name__ == '__main__':
# binary tree formation
root = getnode(1)
root.left = getnode(2)
root.right = getnode(3)
root.left.left = getnode(4)
root.left.right = getnode(5)
root.right.left = getnode(6)
root.right.right = getnode(7)
x = 5
printpath(root, x)
# this code is contributed by pranchalk
c
// c# implementation to print the path from root
// to a given node in a binary tree
using system;
using system.collections;
using system.collections.generic;
class printpath
{
// a node of binary tree
public class node
{
public int data;
public node left, right;
public node(int data)
{
this.data = data;
left = right = null;
}
}
// returns true if there is a path from root
// to the given node. it also populates
// 'arr' with the given path
public static boolean haspath(node root,
list arr, int x)
{
// if root is null
// there is no path
if (root == null)
return false;
// push the node's value in 'arr'
arr.add(root.data);
// if it is the required node
// return true
if (root.data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (haspath(root.left, arr, x) ||
haspath(root.right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// thus, remove current node's value from
// 'arr'and then return false
arr.removeat(arr.count - 1);
return false;
}
// function to print the path from root to the
// given node if the node lies in the binary tree
public static void printpath(node root, int x)
{
// list to store the path
list arr = new list();
// if required node 'x' is present
// then print the path
if (haspath(root, arr, x))
{
for (int i = 0; i < arr.count - 1; i )
console.write(arr[i] "->");
console.write(arr[arr.count - 1]);
}
// 'x' is not present in the binary tree
else
console.write("no path");
}
// driver code
public static void main(string []args)
{
node 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.right.left = new node(6);
root.right.right = new node(7);
int x=5;
printpath(root, x);
}
}
// this code is contributed by arnab kundu
java 描述语言
输出:
1->2->5
时间复杂度:最坏情况下 o(n)，其中 n 为二叉树中的节点数。
本文由阿育什·乔哈里供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
