0993. 二叉树的堂兄弟节点

0993. 二叉树的堂兄弟节点 #

  • 标签:树、广度优先搜索
  • 难度:简单

题目大意 #

给定一个二叉树,和两个值 x,y。从二叉树中找出 x 和 y 对应的节点 node_x,node_y。如果两个节点是堂兄弟节点,则返回 True,否则返回 False。

  • 堂兄弟节点:两个节点的深度相同,父节点不同。

解题思路 #

广度优先搜索或者深度优先搜索都可。以深度优先搜索为例,递归遍历查找节点值为 x,y 的两个节点。在递归的同时,需要传入递归函数当前节点的深度和父节点信息。若找到对应的节点,则保存两节点对应深度和父节点信息。最后判断两个节点是否是深度相同,父节点不同。如果是,则返回 True,不是则返回 False。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        depths = [0, 0]
        parents = [None, None]

        def dfs(node, depth, parent):
            if not node:
                return
            if node.val == x:
                depths[0] = depth
                parents[0] = parent
            elif node.val == y:
                depths[1] = depth
                parents[1] = parent
            dfs(node.left, depth+1, node)
            dfs(node.right, depth+1, node)

        dfs(root, 0, None)
        return depths[0] == depths[1] and parents[0] != parents[1]
本站总访问量  次  |  您是本站第  位访问者