Leetcode 993. 二叉树的堂兄弟节点

题目描述

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

示例 1:

1

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

示例 2:

2

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

示例 3:

3

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

解法1

申请depth和parent分别存储节点值对应的深度和父节点，最后比较两个节点的深度相同，且父节点不同即可。

class Solution(object):
    def isCousins(self, root, x, y):
        """
        :type root: TreeNode
        :type x: int
        :type y: int
        :rtype: bool
        """
        depth={}
        parent={}
        def preOrder(node,dep,pre):
            if node:
                depth[node.val]=dep
                parent[node.val]=pre
                preOrder(node.left,dep+1,node)
                preOrder(node.right,dep+1,node)
        preOrder(root,0,None)
        return depth[x]==depth[y] and parent[x]!=parent[y]

解法2

不申请额外的存储空间，定义findD函数求出两个节点的深度和父节点，再进行比较。

class Solution(object):
    def isCousins(self, root, x, y):
        """
        :type root: TreeNode
        :type x: int
        :type y: int
        :rtype: bool
        """
        self.xd,self.yd=0,0
        self.xp,self.yp=None,None
        self.tmpd,self.tmpp=0,None
        def findD(node,depth,target):
            if node:
                if (node.left and node.left.val==target) or (node.right and node.right.val==target):
                    self.tmpd=depth+1
                    self.tmpp=node
                    return
                findD(node.left,depth+1,target)
                findD(node.right,depth+1,target)
        findD(root,0,x)
        self.xd,self.xp=self.tmpd,self.tmpp
        findD(root,0,y)
        self.yd,self.yp=self.tmpd,self.tmpp
        return self.xd==self.yd and self.xp!=self.yp