This is the 25th day of my participation in Gwen Challenge

describe

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
	
Copy the code

Example 2:

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

Example 3:

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

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
Copy the code

parsing

X and y are Cousins if both nodes are at the same depth of the tree and have different parents. Use DFS recursively, use dictionary D to record the node list of each layer, use r to record the parent node of x and Y, return True if x and y are in the same layer list, and then the parent node is different.

answer

# 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 """ d = {} r = {} def isCousin(root, parent, count): if not root: return if count not in d: d[count] = [] d[count].append(root.val) if (root.val == x or root.val == y) and parent: r[root.val] = parent.val if x in d[count] and y in d[count] and r[x] ! = r[y]: return True return isCousin(root.left, root, count + 1) or isCousin(root.right, root, count + 1) return isCousin(root, None, 0)Copy the code

The results

Given in Python online submissions for Cousins in Binary Tree. Memory Usage: 10000 ms Given in Python online submissions for Cousins in Binary Tree.Copy the code

parsing

The depth of x and y and the parent node are recorded directly, and the result can be judged directly after running the function.

answer

# 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 """ res = [] def dfs(node, parent, depth): if not node: return if node.val == x or node.val == y: res.append((parent, depth)) dfs(node.left, node, depth + 1) dfs(node.right, node, depth + 1) dfs(root, None, 0) node_x, node_y = res return node_x[0] ! = node_y[0] and node_x[1] == node_y[1]Copy the code

The results

Given in Python online submissions for Cousins in Binary Tree. Memory Usage: 10000 ms Submissions in Python online submissions for Cousins in Binary Tree.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation