題目描述
在二叉樹中送朱,根節(jié)點位于深度 0 處娘荡,每個深度為 k 的節(jié)點的子節(jié)點位于深度 k+1 處。
如果二叉樹的兩個節(jié)點深度相同驶沼,但父節(jié)點不同炮沐,則它們是一對堂兄弟節(jié)點。
我們給出了具有唯一值的二叉樹的根節(jié)點 root回怜,以及樹中兩個不同節(jié)點的值 x 和 y大年。
只有與值 x 和 y 對應的節(jié)點是堂兄弟節(jié)點時,才返回 true玉雾。否則翔试,返回 false。
層次遍歷
這里要判斷的是兩個節(jié)點在同一個深度复旬,且父節(jié)點不相同垦缅。可以進行層次遍歷驹碍,判斷兩個節(jié)點是否在同一層壁涎,且父節(jié)點不相同。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
nodes=[root]
while nodes:
flag,vals=False,[]
for i in range(len(nodes)):
node=nodes.pop(0)
if node.left and node.right:
if (node.left.val==x and node.right.val==y) or (node.left.val==y and node.right.val==x):
return False
if node.left:
nodes.append(node.left)
vals.append(node.left.val)
if node.left.val in [x,y]:
flag=True
if node.right:
nodes.append(node.right)
vals.append(node.right.val)
if node.right.val in [x,y]:
flag=True
if flag:
return x in vals and y in vals
return False
遞歸遍歷
因為節(jié)點屬性中沒有父節(jié)點指針志秃,這里不妨定義 par 指向節(jié)點的父節(jié)點粹庞。以 depth 存儲節(jié)點對應的深度,則父節(jié)點不為空時洽损,節(jié)點的深度為父節(jié)點深度加一,父節(jié)點為空革半,則節(jié)點深度為零碑定。因為題目要求還需要判斷兩個節(jié)點的父節(jié)點是否相同,以 parent 存儲節(jié)點對應的父節(jié)點又官。前序遍歷二叉樹延刘,可獲得所有節(jié)點對應的深度及父節(jié)點。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
depth,parent={},{}
def cou(root,par):
if root:
depth[root.val]=depth[par.val]+1 if par else 0
parent[root.val]=par
cou(root.left,root)
cou(root.right,root)
cou(root,None)
return depth[x]==depth[y] and parent[x]!=parent[y]