python使用广度优先搜索算法求解二叉树堂兄弟节点问题

如果给定一颗二叉树，同时给定这颗二叉树中的两个不同节点的值，这里要注意二叉树中的各个节点的值是唯一的，对这两个树节点进行判断是否是堂兄弟节点，堂兄弟节点的意思是处在同一个层级，但是两个节点各有不同的父节点。

添加图片注释，不超过 140 字（可选）

如上图给定的二叉树，对其中的两个节点node1节点是9，node2节点是8，判断这颗树种的这两个节点是否是堂兄弟节点，这里返回的结果是False

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

再给定如上的二叉树，并指定节点node1是4，节点node2是3，这里返回的结果是True，代表4和3节点是堂兄弟节点。

添加图片注释，不超过 140 字（可选）

对于给定条件中二叉树中的节点值都是唯一的，所以要判断两个节点是否为堂兄弟节点首先要做的是定位搜索到这两个节点，其次就是在一个限定条件下可以判断这两个节点是堂兄弟节点，这个限制条件分为两部分，一就是两个节点要处在同一深度，第二就是两个节点的父节点是不同的节点，所以对于解决这个问题，适合采用广度优先搜索算法，借助于队列的形式来对所有节点进行逐层搜索，如果搜索到了指定的节点，则将该节点的深度保存成一个字典，后续即对这字典进行比较，而针对父节点不同的比较，在每个节点入队的时候，就将其深度以及父节点均入队了之后进行比较。

对队列和字典进行初始化，先将根节点入队，这里入队的信息需要有根节点的深度（深度是1），根节点本身以及根节点的父节点（根节点的父节点为空），然后进行迭代过程，将队头的节点取出，判断该节点是否是待判断的节点之一，如果是就将父节点和深度信息进行保存，以供找到两个节点之后再比较，使用python实现的代码如下：

from collections import deque
def Brother(root, node1,node2):
    if not root:
        return False
    queue=deque([(1,root,None)])
    dict_={}
    while queue:
        depth,node,parent=queue.popleft()
        if node.val==node1:
            dict_[node1]=depth
            node1_parent=parent
        if node.val==node2:
            node2_depth=depth
            node2_parent=parent  
        if node.left:
            queue.append((depth+1,node.left,node))
        if node.right:
            queue.append((depth+1,node.right,node))
        if node1_parent and node2_parent:
            break
    return node1_depth==node2_depth and node1_parent!=node2_parent