原文:
给定由不同节点和一对节点组成的二叉树。任务是找到并打印二叉树中两个给定节点之间的路径。
例如，在上面的二叉树中节点 7 和 4 之间的路径是 7 - > 3 - > 1 - > 4 。
这个想法是的路径，并将它们存储在两个独立的向量或数组中，比如路径 1 和路径 2。 现在，出现了两种不同的情况:
- 如果两个节点在根节点的不同子树中。一个在左子树，另一个在右子树。在这种情况下，很明显根节点将位于从节点 1 到节点 2 的路径之间。因此，以相反的顺序打印路径 1，然后打印路径 2。
- 如果节点在同一个子树中。要么在左子树，要么在右子树。在这种情况下，您需要观察从根节点到两个节点的路径将有一个交叉点，在此之前，从根节点到两个节点的路径是公共的。找到该交点，并以类似于上述情况的方式从该点打印节点。
以下是上述方法的实现:
c
// c program to print path between any
// two nodes 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;
}
// function to check if there is a path from root
// to the given node. it also populates
// 'arr' with the given path
bool getpath(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 (getpath(root->left, arr, x) || getpath(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 between
// any two nodes in a binary tree
void printpathbetweennodes(node* root, int n1, int n2)
{
// vector to store the path of
// first node n1 from root
vector path1;
// vector to store the path of
// second node n2 from root
vector path2;
getpath(root, path1, n1);
getpath(root, path2, n2);
int intersection = -1;
// get intersection point
int i = 0, j = 0;
while (i != path1.size() || j != path2.size()) {
// keep moving forward until no intersection
// is found
if (i == j && path1[i] == path2[j]) {
i ;
j ;
}
else {
intersection = j - 1;
break;
}
}
// print the required path
for (int i = path1.size() - 1; i > intersection; i--)
cout << path1[i] << " ";
for (int i = intersection; i < path2.size(); i )
cout << path2[i] << " ";
}
// driver program
int main()
{
// binary tree formation
struct node* root = getnode(0);
root->left = getnode(1);
root->left->left = getnode(3);
root->left->left->left = getnode(7);
root->left->right = getnode(4);
root->left->right->left = getnode(8);
root->left->right->right = getnode(9);
root->right = getnode(2);
root->right->left = getnode(5);
root->right->right = getnode(6);
int node1 = 7;
int node2 = 4;
printpathbetweennodes(root, node1, node2);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print path between any
// two nodes in a binary tree
import java.util.*;
class solution
{
// structure of a node of binary tree
static class node {
int data;
node left, right;
}
/* helper function that allocates a new node with the
given data and null left and right pointers. */
static node getnode(int data)
{
node newnode = new node();
newnode.data = data;
newnode.left = newnode.right = null;
return newnode;
}
// function to check if there is a path from root
// to the given node. it also populates
// 'arr' with the given path
static boolean getpath(node root, vector 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 (getpath(root.left, arr, x) || getpath(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 between
// any two nodes in a binary tree
static void printpathbetweennodes(node root, int n1, int n2)
{
// vector to store the path of
// first node n1 from root
vector path1= new vector();
// vector to store the path of
// second node n2 from root
vector path2=new vector();
getpath(root, path1, n1);
getpath(root, path2, n2);
int intersection = -1;
// get intersection point
int i = 0, j = 0;
while (i != path1.size() || j != path2.size()) {
// keep moving forward until no intersection
// is found
if (i == j && path1.get(i) == path2.get(i)) {
i ;
j ;
}
else {
intersection = j - 1;
break;
}
}
// print the required path
for ( i = path1.size() - 1; i > intersection; i--)
system.out.print( path1.get(i) " ");
for ( i = intersection; i < path2.size(); i )
system.out.print( path2.get(i) " ");
}
// driver program
public static void main(string[] args)
{
// binary tree formation
node root = getnode(0);
root.left = getnode(1);
root.left.left = getnode(3);
root.left.left.left = getnode(7);
root.left.right = getnode(4);
root.left.right.left = getnode(8);
root.left.right.right = getnode(9);
root.right = getnode(2);
root.right.left = getnode(5);
root.right.right = getnode(6);
int node1 = 7;
int node2 = 4;
printpathbetweennodes(root, node1, node2);
}
}
// this code is contributed by arnab kundu
计算机编程语言
# python3 program to print path between any
# two nodes in a binary tree
import sys
import math
# structure of a node of binary tree
class node:
def __init__(self,data):
self.data = data
self.left = none
self.right = none
# helper function that allocates a new node with the
#given data and null left and right pointers.
def getnode(data):
return node(data)
# function to check if there is a path from root
# to the given node. it also populates
# 'arr' with the given path
def getpath(root, rarr, x):
# if root is null
# there is no path
if not root:
return false
# push the node's value in 'arr'
rarr.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 getpath(root.left, rarr, x) or getpath(root.right, rarr, 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
rarr.pop()
return false
# function to print the path between
# any two nodes in a binary tree
def printpathbetweennodes(root, n1, n2):
# vector to store the path of
# first node n1 from root
path1 = []
# vector to store the path of
# second node n2 from root
path2 = []
getpath(root, path1, n1)
getpath(root, path2, n2)
# get intersection point
i, j = 0, 0
intersection=-1
while(i != len(path1) or j != len(path2)):
# keep moving forward until no intersection
# is found
if (i == j and path1[i] == path2[j]):
i = 1
j = 1
else:
intersection = j - 1
break
# print the required path
for i in range(len(path1) - 1, intersection - 1, -1):
print("{} ".format(path1[i]), end = "")
for j in range(intersection 1, len(path2)):
print("{} ".format(path2[j]), end = "")
# driver program
if __name__=='__main__':
# binary tree formation
root = getnode(0)
root.left = getnode(1)
root.left.left = getnode(3)
root.left.left.left = getnode(7)
root.left.right = getnode(4)
root.left.right.left = getnode(8)
root.left.right.right = getnode(9)
root.right = getnode(2)
root.right.left = getnode(5)
root.right.right = getnode(6)
node1=7
node2=4
printpathbetweennodes(root,node1,node2)
# this code is contributed by vikash kumar 37
c
// c# program to print path between any
// two nodes in a binary tree
using system;
using system.collections.generic;
class solution
{
// structure of a node of binary tree
public class node
{
public int data;
public node left, right;
}
/* helper function that allocates a new node with the
given data and null left and right pointers. */
static node getnode(int data)
{
node newnode = new node();
newnode.data = data;
newnode.left = newnode.right = null;
return newnode;
}
// function to check if there is a path from root
// to the given node. it also populates
// 'arr' with the given path
static boolean getpath(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 (getpath(root.left, arr, x) || getpath(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 between
// any two nodes in a binary tree
static void printpathbetweennodes(node root, int n1, int n2)
{
// vector to store the path of
// first node n1 from root
list path1 = new list();
// vector to store the path of
// second node n2 from root
list path2 = new list();
getpath(root, path1, n1);
getpath(root, path2, n2);
int intersection = -1;
// get intersection point
int i = 0, j = 0;
while (i != path1.count || j != path2.count)
{
// keep moving forward until no intersection
// is found
if (i == j && path1[i] == path2[i])
{
i ;
j ;
}
else
{
intersection = j - 1;
break;
}
}
// print the required path
for ( i = path1.count - 1; i > intersection; i--)
console.write( path1[i] " ");
for ( i = intersection; i < path2.count; i )
console.write( path2[i] " ");
}
// driver code
public static void main(string[] args)
{
// binary tree formation
node root = getnode(0);
root.left = getnode(1);
root.left.left = getnode(3);
root.left.left.left = getnode(7);
root.left.right = getnode(4);
root.left.right.left = getnode(8);
root.left.right.right = getnode(9);
root.right = getnode(2);
root.right.left = getnode(5);
root.right.right = getnode(6);
int node1 = 7;
int node2 = 4;
printpathbetweennodes(root, node1, node2);
}
}
// this code is contributed by princi singh
java 描述语言
output:
7 3 1 4
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
