|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +In a binary tree, the root node is at depth 0, and children of each depth k node |
| 4 | +are at depth k+1. |
| 5 | +
|
| 6 | +Two nodes of a binary tree are cousins if they have the same depth, but have |
| 7 | +different parents. |
| 8 | +
|
| 9 | +We are given the root of a binary tree with unique values, and the values x and |
| 10 | +y of two different nodes in the tree. |
| 11 | +
|
| 12 | +Return true if and only if the nodes corresponding to the values x and y are |
| 13 | +cousins. |
| 14 | +
|
| 15 | +Example 1: |
| 16 | +
|
| 17 | +Input: root = [1,2,3,4], x = 4, y = 3 |
| 18 | +Output: false |
| 19 | +Example 2: |
| 20 | +
|
| 21 | +Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 |
| 22 | +Output: true |
| 23 | +Example 3: |
| 24 | +
|
| 25 | +Input: root = [1,2,3,null,4], x = 2, y = 3 |
| 26 | +Output: false |
| 27 | +
|
| 28 | +Note: |
| 29 | +
|
| 30 | +The number of nodes in the tree will be between 2 and 100. |
| 31 | +Each node has a unique integer value from 1 to 100. |
| 32 | +""" |
| 33 | + |
| 34 | +# Definition for a binary tree node. |
| 35 | +classTreeNode: |
| 36 | +def__init__(self,x): |
| 37 | +self.val=x |
| 38 | +self.left=None |
| 39 | +self.right=None |
| 40 | + |
| 41 | + |
| 42 | +classSolution: |
| 43 | +def__init__(self): |
| 44 | +self.pi= [] |
| 45 | +self.depths= [] |
| 46 | + |
| 47 | +defisCousins(self,root:TreeNode,x:int,y:int)->bool: |
| 48 | +""" |
| 49 | + need to know parent and depth |
| 50 | + """ |
| 51 | +self.dfs(None,root,x,0) |
| 52 | +self.dfs(None,root,y,0) |
| 53 | +iflen(self.pi)!=2: |
| 54 | +returnFalse |
| 55 | +returnself.pi[0]!=self.pi[1]andself.depths[0]==self.depths[1] |
| 56 | + |
| 57 | + |
| 58 | +defdfs(self,pi,node,x,depth): |
| 59 | +ifnotnode: |
| 60 | +return |
| 61 | + |
| 62 | +ifnode.val==x: |
| 63 | +self.pi.append(pi) |
| 64 | +self.depths.append(depth) |
| 65 | +return |
| 66 | + |
| 67 | +self.dfs(node,node.left,x,depth+1) |
| 68 | +self.dfs(node,node.right,x,depth+1) |