Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return trueif the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.
Two nodes of a binary tree are cousins if they have the same depth with different parents.
Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.
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
Constraints:
The number of nodes in the tree is in the range [2, 100].
1 <= Node.val <= 100
Each node has a unique value.
x != y
x and y are exist in the tree.
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516171819202122232425
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defisCousins(self,root:Optional[TreeNode],x:int,y:int)->bool:q=deque([(root,None)])depth=0p1=p2=Noned1=d2=Nonewhileq:for_inrange(len(q)):node,parent=q.popleft()ifnode.val==x:p1,d1=parent,depthelifnode.val==y:p2,d2=parent,depthifnode.left:q.append((node.left,node))ifnode.right:q.append((node.right,node))depth+=1returnp1!=p2andd1==d2
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisCousins(root*TreeNode,xint,yint)bool{typepairstruct{node,parent*TreeNode}vard1,d2intvarp1,p2*TreeNodeq:=[]pair{{root,nil}}fordepth:=0;len(q)>0;depth++{forn:=len(q);n>0;n--{node,parent:=q[0].node,q[0].parentq=q[1:]ifnode.Val==x{d1,p1=depth,parent}elseifnode.Val==y{d2,p2=depth,parent}ifnode.Left!=nil{q=append(q,pair{node.Left,node})}ifnode.Right!=nil{q=append(q,pair{node.Right,node})}}}returnd1==d2&&p1!=p2}
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisCousins(root*TreeNode,xint,yint)bool{vard1,d2intvarp1,p2*TreeNodevardfsfunc(root,parent*TreeNode,depthint)dfs=func(root,parent*TreeNode,depthint){ifroot==nil{return}ifroot.Val==x{d1,p1=depth,parent}elseifroot.Val==y{d2,p2=depth,parent}dfs(root.Left,root,depth+1)dfs(root.Right,root,depth+1)}dfs(root,nil,0)returnd1==d2&&p1!=p2}