博客

作为要准备踏入码农行业的人来说，要准备校招，怎么能不去刷刷LeetCode呢？

993. 二叉树的堂兄弟节点

• 题目要求

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

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

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

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

• 例如

省略

• 分析

方法：根据题目要求，要不同的父节点且在同一层存在两个xy才返回True，进行层次遍历判断即可

class Solution(object):
    def isCousins(self, root, x, y):
        first_list=[]
        first_list.append(root)
        if root is None:
            return False
        while first_list:
            fast = []
            length=len(first_list)
            for i in range(length):
                node=first_list.pop(0)
                if node.left and node.right:
                    if x in[node.left.val,node.right.val ] and y  in[node.left.val,node.right.val ] :
                        return False
                if node.left:
                    first_list.append(node.left)
                    fast.append(node.left.val)
                if node.right:
                    first_list.append(node.right)
                    fast.append(node.right.val)
            if x in fast and y in fast:
                return True
        return False

1022. 从根到叶的二进制数之和

• 题目要求

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

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

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

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

• 例如

输入：[1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

• 分析

方法：深度遍历返回每个从根到叶子节点的路径保存进列表，最后将列表路径转换为

class Solution(object):
    def isCousins(self, root, x, y):
        first_list=[]
        first_list.append(root)
        if root is None:
            return False
        while first_list:
            fast = []
            length=len(first_list)
            for i in range(length):
                node=first_list.pop(0)
                if node.left and node.right:
                    if x in[node.left.val,node.right.val ] and y  in[node.left.val,node.right.val ] :
                        return False
                if node.left:
                    first_list.append(node.left)
                    fast.append(node.left.val)
                if node.right:
                    first_list.append(node.right)
                    fast.append(node.right.val)
            if x in fast and y in fast:
                return True
        return False