二叉树的堂兄弟节点

原创

大发明家

发布于 2021-12-06 13:56:53

3600

发布于 2021-12-06 13:56:53

文章被收录于专栏：技术博客文章

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

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

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

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

示例 1：

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

输出：false

示例 2：

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

输出：true

示例 3：

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

输出：false

这是一道标准的二叉树递归搜索问题，当然本人更习惯使用DFS解题。

首先，根据题目定义好的TreeNode可以获取到当前节点的值，以及左子树和右子树。

我们初始化传入节点，父节点(root没有父节点，传自身)，以及最大深度（初始为0）。

遍历过程中比较x,y的数值，并记录深度和父节点，当节点不存在返回即可。

# 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 = right

class Solution:

    def isCousins(self, root, x, y):

        result_x = []

        result_y = []

        def dfs(node,parent,deep):

            if not node:

                return

            nonlocal result_x, result_y

            if node.val == x:

                result_x = [parent,deep]

            elif node.val == y:

                result_y = [parent,deep]

            dfs(node.left,node,deep + 1)

            dfs(node.right,node,deep + 1)

        dfs(root,root,0)

        return result_x[0] != result_y[0] and result_x[1] == result_y[1]

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

作者已关闭评论

0 条评论

热度