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]