![](/contact/xiaochengxu.jpg)
![](/contact/xiaohongshu.jpg)
检查二叉树中的两个节点是否是表兄弟
给定二叉树和两个节点“a”和“b”,确定这两个节点是否是彼此的表兄弟。 如果两个节点处于同一级别并且具有不同的父节点,则它们是彼此的表兄弟。
例子:
6
/ \
3 5
/ \ / \
7 8 1 3
假设两个节点为 7 和 1,结果为 TRUE。
假设两个节点分别为 3 和 5,结果为 FALSE。
假设两个节点分别为 7 和 5,结果为 FALSE。
这个想法是找到一个节点的级别。使用找到的级别,检查“a”和“b”是否处于该级别。如果“a”和“b”处于给定级别,则最后检查它们是不是同一父级的子级。
# Python program to check if two nodes in a binary
# tree are cousins
# A Binary Tree Node
class Node:
# Constructor to create a new Binary Tree
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def isSibling(root, a , b):
# Base Case
if root is None:
return 0
return ((root.left == a and root.right ==b) or
(root.left == b and root.right == a)or
isSibling(root.left, a, b) or
isSibling(root.right, a, b))
# Recursive function to find level of Node 'ptr' in
# a binary tree
def level(root, ptr, lev):
# Base Case
if root is None :
return 0
if root == ptr:
return lev
# Return level if Node is present in left subtree
l = level(root.left, ptr, lev+1)
if l != 0:
return l
# Else search in right subtree
return level(root.right, ptr, lev+1)
# Returns 1 if a and b are cousins, otherwise 0
def isCousin(root,a, b):
# 1. The two nodes should be on the same level in
# the binary tree
# The two nodes should not be siblings(means that
# they should not have the same parent node
if ((level(root,a,1) == level(root, b, 1)) and
not (isSibling(root, a, b))):
return 1
else:
return 0
# Driver program to test above function
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.right
node2 = root.right.right
print ("Yes" if
(root, node1, node2) == 1 else "No")
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
类似的帖子
![](/contact/xiaochengxu.jpg)
![](/contact/xiaohongshu.jpg)