【leetcode】993. Cousins in Binary Tree-蒲公英云

【leetcode】993. Cousins in Binary Tree

亦凉 2022-01-07 11:27 247阅读 0赞

题目如下：

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:
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Example 2:
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Example 3:
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.

解题思路：遍历树，找到对应X和Y的节点，并记录其level和parent即可。

代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    x_p = None
    y_p = None
    x_l = 0
    y_l = 0
    def recursive(self,node,level,parent,x,y):
        if node.val == x:
            self.x_p = parent
            self.x_l = level
        elif node.val == y:
            self.y_p = parent
            self.y_l = level
        if node.left != None:
            self.recursive(node.left,level+1,node,x,y)
        if node.right != None:
            self.recursive(node.right, level + 1, node, x, y)
    def isCousins(self, root, x, y):
        """
        :type root: TreeNode
        :type x: int
        :type y: int
        :rtype: bool
        """
        self.x_p = None
        self.y_p = None
        self.x_l = 0
        self.y_l = 0
        self.recursive(root,0,None,x,y)
        return self.x_p != self.y_p and self.x_l == self.y_l