LeetCode 993. Cousins in Binary Tree

Posted on | In |
Words count in article: 319 | Reading time ≈ 1

题目

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.

Example 1:

1
2
Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

1
2
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

1
2
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

  • The number of nodes in the tree will be between 2 and 100.
  • Each node has a unique integer value from 1 to 100.

思路

Easy题打卡。递归遍历二叉树，找到对应的x和y，并记录其depth和parent是否满足要求即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isCousins(self, root, x, y):
        """
        :type root: TreeNode
        :type x: int
        :type y: int
        :rtype: bool
        """
        self.p_x, self.p_y = None, None
        self.d_x, self.d_y = 0, 0
        self.recursive(root, 0, None, x, y)
        return self.p_x != self.p_y and self.d_x == self.d_y
    
    
    def recursive(self, node, depth, parent, x, y):
        if node.val == x:
            self.p_x = parent
            self.d_x = depth
        elif node.val == y:
            self.p_y = parent
            self.d_y = depth
        if node.left != None:
            self.recursive(node.left, depth+1, node, x, y)
        if node.right != None:
            self.recursive(node.right, depth+1, node, x, y)