Description
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.
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
题目链接：https://leetcode.com/problems/cousins-in-binary-tree/
Difficulty: easy
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.
分析
- 定义一个judge函数用于判断x,y是否为兄弟，判断方式如下：对二叉树做前序遍历，若某一个节点的左节点值等于x且该节点的右节点值等于y，则x，y为兄弟；相反还要做一次判断，x是否为右节点，y是否为左节点；
- 避免为兄弟节点之后，定义get函数获得xy对应节点在树中的深度，若相等则为堂兄弟节点。get是一个前序遍历，index记录深度。
参考代码
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):
def isCousins(self, root, x, y):
def get(ro,tar,index):
if(ro!=None and ro.val==tar):
return index
else:
t=0
if(ro.left):
t=max(t,get(ro.left,tar,index+1))
if(ro.right):
t=max(t,get(ro.right,tar,index+1))
return t
def judge(ro,x,y):
if(ro==None):
return True
else:
jud=True
judx=False
judy=False
if(ro.left):
jud = jud and judge(ro.left,x,y)
if(ro.left.val==x):
judx=True
if(ro.right):
jud = jud and judge(ro.right,x,y)
if(ro.right.val==y):
judy=True
if(judx and judy):
jud=False
return jud
if(not judge(root,x,y) or not judge(root,y,x)):
return False
if(get(root,x,0)==get(root,y,0)):
return True
return False