[leetcode]993. Cousins in Binary Tree(Python)

题目描述

Category：Easy Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.

题目理解

在二叉树中，根节点在深度0，每个深度为k节点的子节点深度为k+1。
一棵二叉树的两个侄子节点要求满足在同一深度但拥有不同父节点。
给定一棵不存在重复值的二叉树，和树中的两个不同节点x和y，如果两个节点为侄子节点返回真。

解题思路

DFS

题目要求的判断条件有两个1.父节点不同，2.高度相同，所以最直白的方法就是把每个节点的父节点和高度都求出来，然后判断x和y这两个节点是不是符合要求即可。
这个题中每个节点的值都不会重复，所以可以直接用值当做key来存储，代码很简单。
思路借鉴：https://blog.csdn.net/fuxuemingzhu/article/details/87867902
都是我抄的 没有我写的 我写不出来

class Solution:
    # Runtime: 32ms 51.67%  MemoryUsage: 13.9MB 6.12%
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        self.m = collections.defaultdict(tuple)
        self.dfs(root, None, 0)
        px, dx = self.m[x]
        py, dy = self.m[y]
        return dx == dy and px != py

    def dfs(self, root, parent ,depth):
        if not root:
            return
        self.m[root.val] = (parent, depth)
        self.dfs(root.left, root, depth + 1)
        self.dfs(root.right, root, depth + 1)

BFS

类似的，不过不用在队列里保存每个节点的高度了，因为在BFS中搜完每一层才向下一层搜索，所以可以很方便的计算每个节点的高度。

class Solution:
	# Runtime: 32ms 51.67%  MemoryUsage: 13.7MB 6.12%
    def isCousins1(self, root: TreeNode, x: int, y: int) -> bool:
        m = collections.defaultdict(tuple)
        q = collections.deque()
        q.append((root, None))
        depth = 0
        while q:
            size = len(q)
            for _ in range(size):
                node, p = q.popleft()
                if not node:
                    continue
                m[node.val] = (p, depth)
                q.append((node.left, node))
                q.append((node.right, node))
            depth += 1
        px, dx = m[x]
        py, dy = m[y]
        return px != py and dx == dy

Time

2020.3.30 天气阴阴的 心情也不太好