原文:
给定具有不同节点的二叉树(没有两个节点具有相同的数据值)。问题是打印从根到两个给定节点 n1 和 n2 的两条路径的公共路径。如果任一节点不存在，则打印“无公共路径”。
示例:
input : 1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
n1 = 4, n2 = 8
output : 1->2
path form root to n1:
1->2->4
path form root to n2:
1->2->5->8
common path:
1->2
进场:以下步骤为:
- 找到两个节点 n1 和 n2 的 lca (最低共同祖先)。参见。
- 如果生命周期评价退出，则打印从根到生命周期评价的路径。参见。否则打印“无公共路径”。
c
// c implementation to print the path common to the
// two paths from the root to the two given nodes
#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 = (struct node*)malloc(sizeof(struct node));
newnode->data = data;
newnode->left = newnode->right = null;
return newnode;
}
// this function returns pointer to lca of two given values n1 and n2.
// v1 is set as true by this function if n1 is found
// v2 is set as true by this function if n2 is found
struct node *findlcautil(struct node* root, int n1, int n2, bool &v1, bool &v2)
{
// base case
if (root == null) return null;
// if either n1 or n2 matches with root's data, report the presence
// by setting v1 or v2 as true and return root (note that if a key
// is ancestor of other, then the ancestor key becomes lca)
if (root->data == n1)
{
v1 = true;
return root;
}
if (root->data == n2)
{
v2 = true;
return root;
}
// look for nodes in left and right subtrees
node *left_lca = findlcautil(root->left, n1, n2, v1, v2);
node *right_lca = findlcautil(root->right, n1, n2, v1, v2);
// if both of the above calls return non-null, then one node
// is present in one subtree and other is present in other,
// so this current node is the lca
if (left_lca && right_lca) return root;
// otherwise check if left subtree or right subtree is lca
return (left_lca != null)? left_lca: right_lca;
}
// returns true if key k is present in tree rooted with root
bool find(node *root, int k)
{
// base case
if (root == null)
return false;
// if key k is present at root, or in left subtree
// or right subtree, return true
if (root->data == k || find(root->left, k) || find(root->right, k))
return true;
// else return false
return false;
}
// this function returns lca of n1 and n2 only if both n1 and n2
// are present in tree, otherwise returns null
node *findlca(node *root, int n1, int n2)
{
// initialize n1 and n2 as not visited
bool v1 = false, v2 = false;
// find lca of n1 and n2
node *lca = findlcautil(root, n1, n2, v1, v2);
// return lca only if both n1 and n2 are present in tree
if (v1 && v2 || v1 && find(lca, n2) || v2 && find(lca, n1))
return lca;
// else return null
return null;
}
// function 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 there 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 common
// to the two paths from the root
// to the two given nodes if the nodes
// lie in the binary tree
void printcommonpath(node *root, int n1, int n2)
{
// vector to store the common path
vector arr;
// lca of node n1 and n2
node *lca = findlca(root, n1, n2);
// if lca of both n1 and n2 exists
if (lca)
{
// then print the path from root to
// lca node
if (haspath(root, arr, lca->data))
{
for (int i=0; i";
cout << arr[arr.size() - 1];
}
}
// lca is not present in the binary tree
// either n1 or n2 or both are not present
else
cout << "no common 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);
root->left->right->left = getnode(8);
root->right->left->right = getnode(9);
int n1 = 4, n2 = 8;
printcommonpath(root, n1, n2);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print the path common to the
// two paths from the root to the two given nodes
import java.util.arraylist;
public class printcommonpath {
// initialize n1 and n2 as not visited
static boolean v1 = false, v2 = false;
// this function returns pointer to lca of two given
// values n1 and n2\. this function assumes that n1 and
// n2 are present in binary tree
static node findlcautil(node node, int n1, int n2)
{
// base case
if (node == null)
return null;
//store result in temp, in case of key match so that we can search for other key also.
node temp=null;
// if either n1 or n2 matches with root's key, report the presence
// by setting v1 or v2 as true and return root (note that if a key
// is ancestor of other, then the ancestor key becomes lca)
if (node.data == n1)
{
v1 = true;
temp = node;
}
if (node.data == n2)
{
v2 = true;
temp = node;
}
// look for keys in left and right subtrees
node left_lca = findlcautil(node.left, n1, n2);
node right_lca = findlcautil(node.right, n1, n2);
if (temp != null)
return temp;
// if both of the above calls return non-null, then one key
// is present in once subtree and other is present in other,
// so this node is the lca
if (left_lca != null && right_lca != null)
return node;
// otherwise check if left subtree or right subtree is lca
return (left_lca != null) ? left_lca : right_lca;
}
// returns true if key k is present in tree rooted with root
static boolean find(node root, int k)
{
// base case
if (root == null)
return false;
// if key k is present at root, or in left subtree
// or right subtree, return true
if (root.data == k || find(root.left, k) || find(root.right, k))
return true;
// else return false
return false;
}
// this function returns lca of n1 and n2 only if both n1 and n2
// are present in tree, otherwise returns null
static node findlca(node root, int n1, int n2)
{
// find lca of n1 and n2
node lca = findlcautil(root, n1, n2);
// return lca only if both n1 and n2 are present in tree
if (v1 && v2 || v1 && find(lca, n2) || v2 && find(lca, n1))
return lca;
// else return null
return null;
}
// function returns true if
// there is a path from root to
// the given node. it also populates
// 'arr' with the given path
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 there 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 common
// to the two paths from the root
// to the two given nodes if the nodes
// lie in the binary tree
static void printcommonpath(node root, int n1, int n2)
{
// arraylist to store the common path
arraylist arr=new arraylist<>();
// lca of node n1 and n2
node lca = findlca(root, n1, n2);
// if lca of both n1 and n2 exists
if (lca!=null)
{
// then print the path from root to
// lca node
if (haspath(root, arr, lca.data))
{
for (int i=0; i");
system.out.print(arr.get(arr.size() - 1));
}
}
// lca is not present in the binary tree
// either n1 or n2 or both are not present
else
system.out.print("no common 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);
root.left.right.left = new node(8);
root.right.left.right = new node(9);
int n1 = 4, n2 = 8;
printcommonpath(root, n1, n2);
}
}
/* class containing left and right child of current
node and key value*/
class node
{
int data;
node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
//this code is contributed by gaurav tiwari
python 3
# python implementation to print the path common to the
# two paths from the root to the two given nodes
# structure of a node of binary tree
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# this function returns pointer to lca of two given values n1 and n2.
# v1 is set as true by this function if n1 is found
# v2 is set as true by this function if n2 is found
def findlcautil(root: node, n1: int, n2: int) -> node:
global v1, v2
# base case
if (root is none):
return none
# if either n1 or n2 matches with root's data, report the presence
# by setting v1 or v2 as true and return root (note that if a key
# is ancestor of other, then the ancestor key becomes lca)
if (root.data == n1):
v1 = true
return root
if (root.data == n2):
v2 = true
return root
# look for nodes in left and right subtrees
left_lca = findlcautil(root.left, n1, n2)
right_lca = findlcautil(root.right, n1, n2)
# if both of the above calls return non-none, then one node
# is present in one subtree and other is present in other,
# so this current node is the lca
if (left_lca and right_lca):
return root
# otherwise check if left subtree or right subtree is lca
return left_lca if (left_lca != none) else right_lca
# returns true if key k is present in tree rooted with root
def find(root: node, k: int) -> bool:
# base case
if (root == none):
return false
# if key k is present at root, or in left subtree
# or right subtree, return true
if (root.data == k or find(root.left, k) or find(root.right, k)):
return true
# else return false
return false
# this function returns lca of n1 and n2 only if both n1 and n2
# are present in tree, otherwise returns none
def findlca(root: node, n1: int, n2: int) -> node:
global v1, v2
# initialize n1 and n2 as not visited
v1 = false
v2 = false
# find lca of n1 and n2
lca = findlcautil(root, n1, n2)
# return lca only if both n1 and n2 are present in tree
if (v1 and v2 or v1 and find(lca, n2) or v2 and find(lca, n1)):
return lca
# else return none
return none
# function returns true if
# there is a path from root to
# the given node. it also populates
# 'arr' with the given path
def haspath(root: node, arr: list, x: int) -> node:
# if root is none
# there is no path
if (root is none):
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 there 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()
return false
# function to print the path common
# to the two paths from the root
# to the two given nodes if the nodes
# lie in the binary tree
def printcommonpath(root: node, n1: int, n2: int):
# vector to store the common path
arr = []
# lca of node n1 and n2
lca = findlca(root, n1, n2)
# if lca of both n1 and n2 exists
if (lca):
# then print the path from root to
# lca node
if (haspath(root, arr, lca.data)):
for i in range(len(arr) - 1):
print(arr[i], end="->")
print(arr[-1])
# lca is not present in the binary tree
# either n1 or n2 or both are not present
else:
print("no common path")
# driver code
if __name__ == "__main__":
v1 = 0
v2 = 0
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(5)
root.right.left = node(6)
root.right.right = node(7)
root.left.right.left = node(8)
root.right.left.right = node(9)
n1 = 4
n2 = 8
printcommonpath(root, n1, n2)
# this code is contributed by
# sanjeev2552
c
// c# implementation to print the path common to the
// two paths from the root to the two given nodes
using system;
using system.collections.generic;
public class printcommonpath
{
// initialize n1 and n2 as not visited
static boolean v1 = false, v2 = false;
// this function returns pointer to lca of two given
// values n1 and n2\. this function assumes that n1 and
// n2 are present in binary tree
static node findlcautil(node node, int n1, int n2)
{
// base case
if (node == null)
return null;
//store result in temp, in case of key
// match so that we can search for other key also.
node temp=null;
// if either n1 or n2 matches with root's key, report the presence
// by setting v1 or v2 as true and return root (note that if a key
// is ancestor of other, then the ancestor key becomes lca)
if (node.data == n1)
{
v1 = true;
temp = node;
}
if (node.data == n2)
{
v2 = true;
temp = node;
}
// look for keys in left and right subtrees
node left_lca = findlcautil(node.left, n1, n2);
node right_lca = findlcautil(node.right, n1, n2);
if (temp != null)
return temp;
// if both of the above calls return non-null, then one key
// is present in once subtree and other is present in other,
// so this node is the lca
if (left_lca != null && right_lca != null)
return node;
// otherwise check if left subtree or right subtree is lca
return (left_lca != null) ? left_lca : right_lca;
}
// returns true if key k is present in tree rooted with root
static boolean find(node root, int k)
{
// base case
if (root == null)
return false;
// if key k is present at root, or in left subtree
// or right subtree, return true
if (root.data == k || find(root.left, k) || find(root.right, k))
return true;
// else return false
return false;
}
// this function returns lca of n1 and n2 only if both n1 and n2
// are present in tree, otherwise returns null
static node findlca(node root, int n1, int n2)
{
// find lca of n1 and n2
node lca = findlcautil(root, n1, n2);
// return lca only if both n1 and n2 are present in tree
if (v1 && v2 || v1 && find(lca, n2) || v2 && find(lca, n1))
return lca;
// else return null
return null;
}
// function returns true if
// there is a path from root to
// the given node. it also populates
// 'arr' with the given path
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 there 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.count-1);
return false;
}
// function to print the path common
// to the two paths from the root
// to the two given nodes if the nodes
// lie in the binary tree
static void printcommonpath(node root, int n1, int n2)
{
// arraylist to store the common path
list arr = new list();
// lca of node n1 and n2
node lca = findlca(root, n1, n2);
// if lca of both n1 and n2 exists
if (lca!=null)
{
// then print the path from root to
// lca node
if (haspath(root, arr, lca.data))
{
for (int i=0; i");
console.write(arr[arr.count - 1]);
}
}
// lca is not present in the binary tree
// either n1 or n2 or both are not present
else
console.write("no common 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);
root.left.right.left = new node(8);
root.right.left.right = new node(9);
int n1 = 4, n2 = 8;
printcommonpath(root, n1, n2);
}
}
/* class containing left and right child of current
node and key value*/
public class node
{
public int data;
public node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
// this code has been contributed by 29ajaykumar
java 描述语言
输出:
1->2
时间复杂度: o(n)，其中 n 为二叉树中的节点数。
本文由阿育什·乔哈里供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
