1. 数据结构与算法/

·300 字·2 分钟· loading
demo007x
作者
demo007x

检查二叉树中的两个节点是否是表兄弟
#

给定二叉树和两个节点“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)