Leetcode 993. 二叉树的堂兄弟节点
题目描述
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
层次遍历
这里要判断的是两个节点在同一个深度，且父节点不相同。可以进行层次遍历，判断两个节点是否在同一层，且父节点不相同。
# 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递归遍历
因为节点属性中没有父节点指针，这里不妨定义 par 指向节点的父节点。以 depth 存储节点对应的深度，则父节点不为空时，节点的深度为父节点深度加一，父节点为空，则节点深度为零。因为题目要求还需要判断两个节点的父节点是否相同，以 parent 存储节点对应的父节点。前序遍历二叉树，可获得所有节点对应的深度及父节点。
# 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]本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.05.25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读