原文:
给定一个二叉树和一个节点，打印给定节点的所有表兄弟。请注意，不应打印兄弟姐妹。
示例:
input : root of below tree
1
/ \
2 3
/ \ / \
4 5 6 7
and pointer to a node say 5.
output : 6, 7
请注意，这与中给定节点的表亲，该二叉树由两个递归遍历组成。在这篇文章中，讨论了一种单层遍历方法。 想法是进行树的级别顺序遍历，因为节点的表亲和兄弟可以在其级别顺序遍历中找到。运行遍历，直到没有找到包含该节点的级别，如果找到，打印给定的级别。
如何打印表亲节点而不是兄弟节点，如何获取队列中该级别的节点？在等级顺序中，当对于父节点，如果父- >左== node_to_find，或者父- >右== node_to_find，那么这个父节点的子节点一定不能被推入队列(因为一个是节点，另一个是它的兄弟节点)。推送队列中同一级别的剩余节点，然后退出循环。当前队列的节点将位于下一个级别(被搜索节点的级别，节点及其同级除外)。现在，打印队列。
下面是上述算法的实现。
c
// c program to print cousins of a node
#include
#include
using namespace std;
// a binary tree node
struct node {
int data;
node *left, *right;
};
// a utility function to create a new binary
// tree node
node* newnode(int item)
{
node* temp = new node;
temp->data = item;
temp->left = temp->right = null;
return temp;
}
// function to print cousins of the node
void printcousins(node* root, node* node_to_find)
{
// if the given node is the root itself,
// then no nodes would be printed
if (root == node_to_find) {
cout << "cousin nodes : none" << endl;
return;
}
queue q;
bool found = false;
int size_;
node* p;
q.push(root);
// the following loop runs until found is
// not true, or q is not empty.
// if found has become true => we have found
// the level in which the node is present
// and the present queue will contain all the
// cousins of that node
while (!q.empty() && !found) {
size_ = q.size();
while (size_) {
p = q.front();
q.pop();
// if current node's left or right child
// is the same as the node to find,
// then make found = true, and don't push
// any of them into the queue, as
// we don't have to print the siblings
if ((p->left == node_to_find ||
p->right == node_to_find)) {
found = true;
}
else {
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
size_--;
}
}
// if found == true then the queue will contain the
// cousins of the given node
if (found) {
cout << "cousin nodes : ";
size_ = q.size();
// size_ will be 0 when the node was at the
// level just below the root node.
if (size_ == 0)
cout << "none";
for (int i = 0; i < size_; i ) {
p = q.front();
q.pop();
cout << p->data << " ";
}
}
else {
cout << "node not found";
}
cout << endl;
return;
}
// driver program to test above function
int main()
{
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(15);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
node* x = newnode(43);
printcousins(root, x);
printcousins(root, root);
printcousins(root, root->right);
printcousins(root, root->left);
printcousins(root, root->left->right);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print
// cousins of a node
import java.io.*;
import java.util.*;
import java.lang.*;
// a binary tree node
class node
{
int data;
node left, right;
node(int key)
{
data = key;
left = right = null;
}
}
class gfg
{
// function to print
// cousins of the node
static void printcousins(node root,
node node_to_find)
{
// if the given node
// is the root itself,
// then no nodes would
// be printed
if (root == node_to_find)
{
system.out.print("cousin nodes :"
" none" "\n");
return;
}
queue q = new linkedlist();
boolean found = false;
int size_ = 0;
node p = null;
q.add(root);
// the following loop runs
// until found is not true,
// or q is not empty. if
// found has become true => we
// have found the level in
// which the node is present
// and the present queue will
// contain all the cousins of
// that node
while (q.isempty() == false &&
found == false)
{
size_ = q.size();
while (size_ -- > 0)
{
p = q.peek();
q.remove();
// if current node's left
// or right child is the
// same as the node to find,
// then make found = true,
// and don't push any of them
// into the queue, as we don't
// have to print the siblings
if ((p.left == node_to_find ||
p.right == node_to_find))
{
found = true;
}
else
{
if (p.left != null)
q.add(p.left);
if (p.right!= null)
q.add(p.right);
}
}
}
// if found == true then the
// queue will contain the
// cousins of the given node
if (found == true)
{
system.out.print("cousin nodes : ");
size_ = q.size();
// size_ will be 0 when
// the node was at the
// level just below the
// root node.
if (size_ == 0)
system.out.print("none");
for (int i = 0; i < size_; i )
{
p = q.peek();
q.poll();
system.out.print(p.data " ");
}
}
else
{
system.out.print("node not found");
}
system.out.println("");
return;
}
// 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.left.right.right = new node(15);
root.right.left = new node(6);
root.right.right = new node(7);
root.right.left.right = new node(8);
node x = new node(43);
printcousins(root, x);
printcousins(root, root);
printcousins(root, root.right);
printcousins(root, root.left);
printcousins(root, root.left.right);
}
}
python 3
# python3 program to print cousins of a node
# a binary tree node
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# a utility function to create a new binary
# tree node
def newnode(item):
temp = node(item)
return temp
# function to print cousins of the node
def printcousins(root, node_to_find):
# if the given node is the root itself,
# then no nodes would be printed
if (root == node_to_find):
print("cousin nodes : none")
return;
q = []
found = false;
size_ = 0
p = none
q.append(root);
# the following loop runs until found is
# not true, or q is not empty.
# if found has become true => we have found
# the level in which the node is present
# and the present queue will contain all the
# cousins of that node
while (len(q) != 0 and not found):
size_ = len(q)
while (size_ != 0):
p = q[0]
q.pop(0);
# if current node's left or right child
# is the same as the node to find,
# then make found = true, and don't append
# any of them into the queue, as
# we don't have to print the siblings
if ((p.left == node_to_find or p.right == node_to_find)):
found = true;
else:
if (p.left):
q.append(p.left);
if (p.right):
q.append(p.right);
size_-=1
# if found == true then the queue will contain the
# cousins of the given node
if (found):
print("cousin nodes : ", end='')
size_ = len(q)
# size_ will be 0 when the node was at the
# level just below the root node.
if (size_ == 0):
print("none", end='')
for i in range(0, size_):
p = q[0]
q.pop(0);
print(p.data, end=' ')
else:
print("node not found", end='')
print()
return;
# driver program to test above function
if __name__=='__main__':
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(15);
root.right.left = newnode(6);
root.right.right = newnode(7);
root.right.left.right = newnode(8);
x = newnode(43);
printcousins(root, x);
printcousins(root, root);
printcousins(root, root.right);
printcousins(root, root.left);
printcousins(root, root.left.right);
# this code is contributed by rutvik_56
c
// c# program to print
// cousins of a node
using system;
using system.collections.generic;
// a binary tree node
public class node
{
public int data;
public node left, right;
public node(int key)
{
data = key;
left = right = null;
}
}
public class gfg
{
// function to print
// cousins of the node
static void printcousins(node root,
node node_to_find)
{
// if the given node
// is the root itself,
// then no nodes would
// be printed
if (root == node_to_find)
{
console.write("cousin nodes :"
" none" "\n");
return;
}
queue q = new queue();
bool found = false;
int size_ = 0;
node p = null;
q.enqueue(root);
// the following loop runs
// until found is not true,
// or q is not empty. if
// found has become true => we
// have found the level in
// which the node is present
// and the present queue will
// contain all the cousins of
// that node
while (q.count!=0 &&
found == false)
{
size_ = q.count;
while (size_ -- > 0)
{
p = q.peek();
q.dequeue();
// if current node's left
// or right child is the
// same as the node to find,
// then make found = true,
// and don't push any of them
// into the queue, as we don't
// have to print the siblings
if ((p.left == node_to_find ||
p.right == node_to_find))
{
found = true;
}
else
{
if (p.left != null)
q.enqueue(p.left);
if (p.right!= null)
q.enqueue(p.right);
}
}
}
// if found == true then the
// queue will contain the
// cousins of the given node
if (found == true)
{
console.write("cousin nodes : ");
size_ = q.count;
// size_ will be 0 when
// the node was at the
// level just below the
// root node.
if (size_ == 0)
console.write("none");
for (int i = 0; i < size_; i )
{
p = q.peek();
q.dequeue();
console.write(p.data " ");
}
}
else
{
console.write("node not found");
}
console.writeline("");
return;
}
// 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.left.right.right = new node(15);
root.right.left = new node(6);
root.right.right = new node(7);
root.right.left.right = new node(8);
node x = new node(43);
printcousins(root, x);
printcousins(root, root);
printcousins(root, root.right);
printcousins(root, root.left);
printcousins(root, root.left.right);
}
}
// this code is contributed rajput-ji
java 描述语言
output:
node not found
cousin nodes : none
cousin nodes : none
cousin nodes : none
cousin nodes : 6 7
时间复杂度:这是单级顺序遍历，因此时间复杂度= o(n)，辅助空间= o(n)(参见)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
