题目

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

卡点

这道题我想到了使用bfs遍历树并且去记录深度，但有两点未思考到

  • 深度记录的方式应该是和节点绑定，即每个节点应该有自己的深度变量。我试图通过一个变量记录深度，结果难以通过队列的变化确定（应该可以通过遍历前记录队列中节点数量，然后for循环遍历完成后对全局深度+1）

  • dfs和bfs都可以在遍历前去获取到父节点信息，而且是要在对节点进行操作之前，bfs是在入队列前，而我在思考的时候是思考的节点进入队列后如何判断它的父节点。当然这里也可以判断，如果我不使用队列，而是使用一个数据，元素不停的加入，而元素的pop是通过移动一个队首的指针完成，那么我就可以通过下标运算得到父节点的值，但这样内存消耗会大一些。

答案

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# dfs
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        queue = []
        queue.append((root,0))
        x_found, x_parent, x_deep = False, None, -1
        y_found, y_parent, y_deep = False, None, -1
        while len(queue) > 0:
            node, parent_deep = queue.pop(0)
            if node.left != None:
                if node.left.val == x:
                    x_found = True
                    x_parent = node
                    x_deep = parent_deep + 1
                elif node.left.val == y:
                    y_found = True
                    y_parent = node
                    y_deep = parent_deep + 1
                queue.append((node.left, parent_deep+1))
            if node.right != None:
                if node.right.val == x:
                    x_found = True
                    x_parent = node
                    x_deep = parent_deep + 1
                elif node.right.val == y:
                    y_found = True
                    y_parent = node
                    y_deep = parent_deep + 1
                queue.append((node.right, parent_deep+1))
            if x_found and y_found:
                break
        return x_found and y_found and x_deep == y_deep and x_parent != y_parent