# 算法题：检查二叉树中的两个节点是否是表亲 |S2

2021年3月25日13:13:32 发表评论 484 次浏览

## 本文概述

``````6
/   \
3     5
/ \   / \
7   8 1   3
Say two node be 7 and 1, result is TRUE.
Say two nodes are 3 and 5, result is FALSE.
Say two nodes are 7 and 5, result is FALSE.``````

## C ++

``````// CPP program to check if two Nodes in
// a binary tree are cousins
// using level-order traversals
#include <bits/stdc++.h>
using namespace std;

// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};

// A utility function to create a new
// Binary Tree Node
struct Node* newNode( int item)
{
struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}

// Returns true if a and b are cousins, // otherwise false.
bool isCousin(Node* root, Node* a, Node* b)
{
if (root == NULL)
return false ;

// To store parent of node a.
Node* parA = NULL;

// To store parent of node b.
Node* parB = NULL;

// queue to perform level order
// traversal. Each element of
// queue is a pair of node and
// its parent.
queue<pair<Node*, Node*> > q;

// Dummy node to act like parent
// of root node.
Node* tmp = newNode(-1);

// To store front element of queue.
pair<Node*, Node*> ele;

// Push root to queue.
q.push(make_pair(root, tmp));
int levSize;

while (!q.empty()) {

// find number of elements in
// current level.
levSize = q.size();
while (levSize) {

ele = q.front();
q.pop();

// check if current node is node a
// or node b or not.
if (ele.first->data == a->data) {
parA = ele.second;
}

if (ele.first->data == b->data) {
parB = ele.second;
}

// push children of current node
// to queue.
if (ele.first->left) {
q.push(make_pair(ele.first->left, ele.first));
}

if (ele.first->right) {
q.push(make_pair(ele.first->right, ele.first));
}

levSize--;

// If both nodes are found in
// current level then no need
// to traverse current level further.
if (parA && parB)
break ;
}

// Check if both nodes are siblings
// or not.
if (parA && parB) {
return parA != parB;
}

// If one node is found in current level
// both nodes are not cousins.
if ((parA && !parB) || (parB && !parA)) {
return false ;
}
}

return false ;
}
// Driver Code
int main()
{
/*
1
/  \
2    3
/ \  / \
4   5 6  7
\ \
15 8
*/

struct 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);

struct Node *Node1, *Node2;
Node1 = root->left->left;
Node2 = root->right->right;

isCousin(root, Node1, Node2) ? puts ( "Yes" ) : puts ( "No" );

return 0;
}``````

## Java

``````// Java program to check if two Nodes in
// a binary tree are cousins
// using level-order traversals
import java.util.*;
import javafx.util.Pair;

// User defined node class
class Node
{
int data;
Node left, right;

// Constructor to create a new tree node
Node( int item)
{
data = item;
left = right = null ;
}
}

class BinaryTree
{
Node root;

// Returns true if a and b are cousins, // otherwise false.
boolean isCousin(Node node, Node a, Node b)
{
if (node == null )
return false ;

// To store parent of node a.
Node parA = null ;

// To store parent of node b.
Node parB = null ;

// queue to perform level order
// traversal. Each element of
// queue is a pair of node and
// its parent.
Queue<Pair <Node, Node>> q = new LinkedList<> ();

// Dummy node to act like parent
// of root node.
Node tmp = new Node(- 1 );

// To store front element of queue.
Pair<Node, Node> ele;

// Push root to queue.
q.add( new Pair <Node, Node> (node, tmp));

int levelSize;

while (!q.isEmpty())
{

// find number of elements in
// current level.
levelSize = q.size();
while (levelSize != 0 )
{
ele = q.peek();
q.remove();

// check if current node is node a
// or node b or not.
if (ele.getKey().data == a.data)
parA = ele.getValue();

if (ele.getKey().data == b.data)
parB = ele.getValue();

// push children of current node
// to queue.
if (ele.getKey().left != null )

if (ele.getKey().right != null )

levelSize--;

// If both nodes are found in
// current level then no need
// to traverse current level further.
if (parA != null && parB != null )
break ;
}

// Check if both nodes are siblings
// or not.
if (parA != null && parB != null )
return parA != parB;

// If one node is found in current level
// both nodes are not cousins.
if ((parA!= null && parB== null ) || (parB!= null && parA== null ))
return false ;
}

return false ;
}

// Driver code
public static void main(String args[])
{
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.left.right.right = new Node( 15 );
tree.root.right.left = new Node( 6 );
tree.root.right.right = new Node( 7 );
tree.root.right.left.right = new Node( 8 );

Node Node1, Node2;
Node1 = tree.root.left.right.right;
Node2 = tree.root.right.left.right;
if (tree.isCousin(tree.root, Node1, Node2))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}

// This code is contributed by shubham96301``````

## Python3

``````# Python3 program to check if two
# Nodes in a binary tree are cousins
# using level-order traversals

# A Binary Tree Node
class Node:

def __init__( self , item):
self .data = item
self .left = None
self .right = None

# Returns True if a and b
# are cousins, otherwise False.
def isCousin(root, a, b):

if root = = None :
return False

# To store parent of node a.
parA = None

# To store parent of node b.
parB = None

# queue to perform level order
# traversal. Each element of queue
# is a pair of node and its parent.
q = []

# Dummy node to act like
# parent of root node.
tmp = Node( - 1 )

# Push root to queue.
q.append((root, tmp))

while len (q) > 0 :

# find number of elements in
# current level.
levSize = len (q)
while levSize:

ele = q.pop( 0 )

# check if current node is
# node a or node b or not.
if ele[ 0 ].data = = a.data:
parA = ele[ 1 ]

if ele[ 0 ].data = = b.data:
parB = ele[ 1 ]

# push children of
# current node to queue.
if ele[ 0 ].left:
q.append((ele[ 0 ].left, ele[ 0 ]))

if ele[ 0 ].right:
q.append((ele[ 0 ].right, ele[ 0 ]))
levSize - = 1

# If both nodes are found in
# current level then no need
# to traverse current level further.
if parA and parB:
break

# Check if both nodes
# are siblings or not.
if parA and parB:
return parA ! = parB

# If one node is found in current level
# both nodes are not cousins.
if (parA and not parB) or (parB and not parA):
return False

return False

# Driver Code
if __name__ = = '__main__' :

root = Node( 1 )
root.left = Node( 2 )
root.right = Node( 3 )
root.left.left = Node( 4 )
root.left.right = Node( 5 )
root.left.right.right = Node( 15 )
root.right.left = Node( 6 )
root.right.right = Node( 7 )
root.right.left.right = Node( 8 )

Node1 = root.left.left
Node2 = root.right.right

if isCousin(root, Node1, Node2):
print ( 'Yes' )
else :
print ( 'No' )

# This code is contributed by Rituraj Jain``````

## C#

``````// C# program to check if two Nodes in
// a binary tree are cousins
// using level-order traversals
using System;
using System.Collections.Generic;

// User defined node class
public class Node
{
public int data;
public Node left, right;

// Constructor to create a new tree node
public Node( int item)
{
data = item;
left = right = null ;
}
}
// User defined pair class
public class Pair
{

public Node first, second;

// Constructor to create a new tree node
public Pair(Node first, Node second)
{
this .first = first;
this .second = second;
}
}

class BinaryTree
{
Node root;

// Returns true if a and b are cousins, // otherwise false.
Boolean isCousin(Node node, Node a, Node b)
{
if (node == null )
return false ;

// To store parent of node a.
Node parA = null ;

// To store parent of node b.
Node parB = null ;

// queue to perform level order
// traversal. Each element of
// queue is a pair of node and
// its parent.
Queue<Pair > q = new Queue<Pair > ();

// Dummy node to act like parent
// of root node.
Node tmp = new Node(-1);

// To store front element of queue.
Pair ele;

// Push root to queue.
q.Enqueue( new Pair (node, tmp));

int levelSize;

while (q.Count>0)
{

// find number of elements in
// current level.
levelSize = q.Count;
while (levelSize != 0)
{
ele = q.Peek();
q.Dequeue();

// check if current node is node a
// or node b or not.
if (ele.first.data == a.data)
parA = ele.second;

if (ele.first.data == b.data)
parB = ele.second;

// push children of current node
// to queue.
if (ele.first.left != null )
q.Enqueue( new Pair(ele.first.left, ele.first));

if (ele.first.right != null )
q.Enqueue( new Pair(ele.first.right, ele.first));

levelSize--;

// If both nodes are found in
// current level then no need
// to traverse current level further.
if (parA != null && parB != null )
break ;
}

// Check if both nodes are siblings
// or not.
if (parA != null && parB != null )
return parA != parB;

// If one node is found in current level
// both nodes are not cousins.
if ((parA != null && parB == null ) || (parB != null && parA == null ))
return false ;
}

return false ;
}

// Driver code
public static void Main(String []args)
{
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.left.right.right = new Node(15);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.right.left.right = new Node(8);

Node Node1, Node2;
Node1 = tree.root.left.right.right;
Node2 = tree.root.right.left.right;
if (tree.isCousin(tree.root, Node1, Node2))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}

// This code is contributed by Arnab Kundu``````

``Yes``