LeetCode 第 993 题:二叉树的堂兄弟节点

Python publisher01 43℃

说明:本文是根据自己在 LeetCode 中文网站上发布的题解写成的,即自己转载了自己的文章。
原文地址:
https://leetcode-cn.com/problems/cousins-in-binary-tree/solution/yan-du-you-xian-bian-li-python-dai-ma-by-liweiwei1/

1、紧抓堂兄弟结点的定义:如果二叉树的两个节点深度相同,但父节点不同,则它们是一对堂兄弟节点。很显然,可以使用层序优先遍历(广度优先遍历)。

2、二叉树的两个节点深度相同,这里的“深度”,即经过层序优先遍历以后,两个结点在同一层;

3、满足在同一层的前提下,如何判断“父节点不同”呢?我们把父节点相同这件事情排除掉就好啦。具体做法是:如果子结点为空时,设置一个占位的数值。因为题目中说“每个结点的值都是唯一的、范围为 1100 的整数”。因此可以把空结点设置为一个不在 1100 中间的数,例如 0。这样在层序遍历中检查,如果两个索引序号相邻,并且索引序号小的索引序号是偶数,索引序号大的索引序号是奇数,那么就表示它们的父结点相同,遇到这种情况,直接返回 False,也不用往下看了。不是这种情况的话,可以返回 True

下面看几个具体的例子:


image.png

image.png

Python 代码:

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':
        if not root:
            return False
        queue = [root]
        while queue:
            # 循环开始时,队列中的元素个数就是当前层结点的个数
            size = len(queue)
            # 把一层的结点值都放进来,如果遇到空结点,放置 0,
            # 题目中说"每个节点的值都是唯一的、范围为 1 到 100 的整数。"
            # 所以,你放 101 都是可以的
            cur_level = []
            for _ in range(size):
                top = queue.pop(0)
                if top:
                    cur_level.append(top.val)
                    queue.append(top.left)
                    queue.append(top.right)
                else:
                    cur_level.append(0)
            # 如果这两个索引都在一层,只有一种情况需要排除
            # 那就是两个结点挨着,并且索引小的结点的索引是偶数
            if x in cur_level and y in cur_level:
                index1 = cur_level.index(x)
                index2 = cur_level.index(y)
                if index1 > index2:
                    index1, index2 = index2, index1
                if index1 + 1 == index2 and index1 & 1 == 0:
                    return False
                return True
            # 如果索引不在同一层,直接就可以返回不是堂兄弟结点了
            if x in cur_level or y in cur_level:
                return False
        return False

转载请注明:Python量化投资 » LeetCode 第 993 题:二叉树的堂兄弟节点

喜欢 (0)or分享 (0)