原文:
给定一个二叉树和两个节点，任务是打印二叉树中两个给定节点的所有公共节点。
示例:
given binary tree is :
1
/ \
2 3
/ \ / \
4 5 6 7
/ / \
8 9 10
given nodes 9 and 7, so the common nodes are:-
1, 3
问于:
- 求给定两个节点的 。
- 打印 lca 的所有祖先，如本所做的，也打印 lca。
c
// c program to find common nodes for given two nodes
#include
using namespace std;
// a binary tree node
struct node {
struct node* left, *right;
int key;
};
// utility function to create a new tree node
node* newnode(int key)
{
node* temp = new node;
temp->key = key;
temp->left = temp->right = null;
return temp;
}
// utility function to find the lca of two given values
// n1 and n2.
struct node* findlca(struct node* root, int n1, int n2)
{
// base case
if (root == null)
return null;
// if either n1 or n2 matches with root's key,
// report the presence by returning root (note
// that if a key is ancestor of other, then the
// ancestor key becomes lca
if (root->key == n1 || root->key == n2)
return root;
// look for keys in left and right subtrees
node* left_lca = findlca(root->left, n1, n2);
node* right_lca = findlca(root->right, n1, n2);
// 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 && right_lca)
return root;
// otherwise check if left subtree or right
// subtree is lca
return (left_lca != null) ? left_lca : right_lca;
}
// utility function to print all ancestors of lca
bool printancestors(struct node* root, int target)
{
/* base cases */
if (root == null)
return false;
if (root->key == target) {
cout << root->key << " ";
return true;
}
/* if target is present in either left or right
subtree of this node, then print this node */
if (printancestors(root->left, target) ||
printancestors(root->right, target)) {
cout << root->key << " ";
return true;
}
/* else return false */
return false;
}
// function to find nodes common to given two nodes
bool findcommonnodes(struct node* root, int first,
int second)
{
struct node* lca = findlca(root, first, second);
if (lca == null)
return false;
printancestors(root, lca->key);
}
// driver program to test above functions
int main()
{
// let us create binary tree given in the above
// example
node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->left->left->left = newnode(8);
root->right->left->left = newnode(9);
root->right->left->right = newnode(10);
if (findcommonnodes(root, 9, 7) == false)
cout << "no common nodes";
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to find common nodes for given two nodes
import java.util.linkedlist;
// class to represent tree node
class node
{
int data;
node left, right;
public node(int item)
{
data = item;
left = null;
right = null;
}
}
// class to count full nodes of tree
class binarytree
{
static node root;
// utility function to find the lca of two given values
// n1 and n2.
static node findlca(node root, int n1, int n2)
{
// base case
if (root == null)
return null;
// if either n1 or n2 matches with root's key,
// report the presence by returning root (note
// that if a key is ancestor of other, then the
// ancestor key becomes lca
if (root.data == n1 || root.data == n2)
return root;
// look for keys in left and right subtrees
node left_lca = findlca(root.left, n1, n2);
node right_lca = findlca(root.right, n1, n2);
// 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 root;
// otherwise check if left subtree or right
// subtree is lca
return (left_lca != null) ? left_lca : right_lca;
}
// utility function to print all ancestors of lca
static boolean printancestors(node root, int target)
{
/* base cases */
if (root == null)
return false;
if (root.data == target) {
system.out.print(root.data " ");
return true;
}
/* if target is present in either left or right
subtree of this node, then print this node */
if (printancestors(root.left, target) ||
printancestors(root.right, target)) {
system.out.print(root.data " ");
return true;
}
/* else return false */
return false;
}
// function to find nodes common to given two nodes
static boolean findcommonnodes(node root, int first,
int second)
{
node lca = findlca(root, first, second);
if (lca == null)
return false;
printancestors(root, lca.data);
return true;
}
// driver program to test above functions
public static void main(string args[])
{
/*let us create binary tree shown in
above example */
binarytree tree = new binarytree();
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.right.left = new node(6);
tree.root.right.right = new node(7);
tree.root.left.left.left = new node(8);
tree.root.right.left.left = new node(9);
tree.root.right.left.right = new node(10);
if (findcommonnodes(root, 9, 7) == false)
system.out.println("no common nodes");
}
}
// this code is contributed by mr somesh awasthi
python 3
# python3 program to find common
# nodes for given two nodes
# utility class to create a new tree node
class newnode:
def __init__(self, key):
self.key = key
self.left = self.right = none
# utility function to find the lca of
# two given values n1 and n2.
def findlca(root, n1, n2):
# base case
if (root == none):
return none
# if either n1 or n2 matches with root's key,
# report the presence by returning root (note
# that if a key is ancestor of other, then the
# ancestor key becomes lca
if (root.key == n1 or root.key == n2):
return root
# look for keys in left and right subtrees
left_lca = findlca(root.left, n1, n2)
right_lca = findlca(root.right, n1, n2)
# if both of the above calls return non-none,
# then one key is present in once subtree and
# other is present in other, so this node is the lca
if (left_lca and right_lca):
return root
# otherwise check if left subtree or
# right subtree is lca
if (left_lca != none):
return left_lca
else:
return right_lca
# utility function to print all ancestors of lca
def printancestors(root, target):
# base cases
if (root == none):
return false
if (root.key == target):
print(root.key, end = " ")
return true
# if target is present in either left or right
# subtree of this node, then prthis node
if (printancestors(root.left, target) or
printancestors(root.right, target)):
print(root.key, end = " ")
return true
# else return false
return false
# function to find nodes common to given two nodes
def findcommonnodes(root, first, second):
lca = findlca(root, first, second)
if (lca == none):
return false
printancestors(root, lca.key)
# driver code
if __name__ == '__main__':
# let us create binary tree given
# in the above example
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(5)
root.right.left = newnode(6)
root.right.right = newnode(7)
root.left.left.left = newnode(8)
root.right.left.left = newnode(9)
root.right.left.right = newnode(10)
if (findcommonnodes(root, 9, 7) == false):
print("no common nodes")
# this code is contributed by pranchalk
c
using system;
// c# program to find common nodes for given two nodes
// class to represent tree node
public class node
{
public int data;
public node left, right;
public node(int item)
{
data = item;
left = null;
right = null;
}
}
// class to count full nodes of tree
public class binarytree
{
public static node root;
// utility function to find the lca of two given values
// n1 and n2.
public static node findlca(node root, int n1, int n2)
{
// base case
if (root == null)
{
return null;
}
// if either n1 or n2 matches with root's key,
// report the presence by returning root (note
// that if a key is ancestor of other, then the
// ancestor key becomes lca
if (root.data == n1 || root.data == n2)
{
return root;
}
// look for keys in left and right subtrees
node left_lca = findlca(root.left, n1, n2);
node right_lca = findlca(root.right, n1, n2);
// 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 root;
}
// otherwise check if left subtree or right
// subtree is lca
return (left_lca != null) ? left_lca : right_lca;
}
// utility function to print all ancestors of lca
public static bool printancestors(node root, int target)
{
/* base cases */
if (root == null)
{
return false;
}
if (root.data == target)
{
console.write(root.data " ");
return true;
}
/* if target is present in either left or right
subtree of this node, then print this node */
if (printancestors(root.left, target)
|| printancestors(root.right, target))
{
console.write(root.data " ");
return true;
}
/* else return false */
return false;
}
// function to find nodes common to given two nodes
public static bool findcommonnodes(node root,
int first, int second)
{
node lca = findlca(root, first, second);
if (lca == null)
{
return false;
}
printancestors(root, lca.data);
return true;
}
// driver program to test above functions
public static void main(string[] args)
{
/*let us create binary tree shown in
above example */
binarytree tree = new binarytree();
binarytree.root = new node(1);
binarytree.root.left = new node(2);
binarytree.root.right = new node(3);
binarytree.root.left.left = new node(4);
binarytree.root.left.right = new node(5);
binarytree.root.right.left = new node(6);
binarytree.root.right.right = new node(7);
binarytree.root.left.left.left = new node(8);
binarytree.root.right.left.left = new node(9);
binarytree.root.right.left.right = new node(10);
if (findcommonnodes(root, 9, 7) == false)
{
console.writeline("no common nodes");
}
}
}
// this code is contributed by shrikant13
java 描述语言
输出:
3 1
本文由 供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
