【leetcode】993. Cousins in Binary Tree

亦凉 2022-01-07 11:27 227阅读 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:  
> ![q1248-01.png][]
> 
>     Input: root = [1,2,3,4], x = 4, y = 3
>     Output: false
> 
> Example 2:  
> ![q1248-02.png][]
> 
>     Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
>     Output: true
> 
> Example 3:
> 
> ![q1248-03.png][]
> 
>     Input: root = [1,2,3,null,4], x = 2, y = 3
>     Output: false
> 
> Note:
> 
> 1.  The number of nodes in the tree will be between `2` and `100`.
> 2.  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

转载于:https://www.cnblogs.com/seyjs/p/10410669.html

[q1248-01.png]: https://assets.leetcode.com/uploads/2019/02/12/q1248-01.png
[q1248-02.png]: https://assets.leetcode.com/uploads/2019/02/12/q1248-02.png
[q1248-03.png]: https://assets.leetcode.com/uploads/2019/02/13/q1248-03.png