LeetCode0993: 二叉树的堂兄弟节点

题目介绍

描述：

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

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

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

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

解题思路：

递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

二叉树题目的一个难点在于如何通过题目的要求思考出每一个节点需要做什么

二叉树解题策略

一递归二队列 + 迭代（层次遍历）三栈 + 迭代（非递归遍历）四其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

自己的解法实现

def isCousins4(self, root, x, y):
        if not root: return []
        stack = [root]
        while stack:
            counter = 0
            for _ in range(len(stack)):
                node = stack.pop(0)
                if node.left and node.right and ((node.left.val == x and node.right.val == y) or (node.left.val == x and node.right.val == y)):
                    return False
                if node.val == x or node.val == y:
                    counter += 1
                    if counter == 2:
                        return True
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)

网上比较优秀的解法

解法一

方法：标记父节点与深度思路当且仅当一对节点深度相同而父节点不相同时，它们是堂兄弟节点。一种非常直接的方法就是通过某种方法求出每一个节点的深度与父节点。

算法我们用深度优先搜索标记每一个节点，对于每一个节点 node，它的父亲为 par，深度为 d，我们将其记录到 Hashmap 中：parent[node.val] = par 且 depth[node.val] = d。

def isCousins(self, root, x, y):
        parent = {}
        depth = {}
        def dfs(node, par = None):
            if node:
                depth[node.val] = 1 + depth[par.val] if par else 0
                parent[node.val] = par
                dfs(node.left, node)
                dfs(node.right, node)
        dfs(root)
        return depth[x] == depth[y] and parent[x] != parent[y]

解法二

方法1——深度优先搜索输出x和y的深度以及它们的父结点，然后按照题意比较即可

def __init__(self):
        self.d = 0
        self.node = TreeNode()

    def isCousins2(self, root, x, y):
        def dfs(node, num, tmp):
            if not node: return
            tmp += 1
            if (node.left and node.left.val == num) or (node.right and node.right.val == num):
                self.d = tmp + 1
                self.node = node
                return
            dfs(node.left, num, tmp)
            dfs(node.right, num, tmp)
        dfs(root, x, 0)
        dx, xf = self.d, self.node

        dfs(root, y, 0)
        dy, yf = self.d, self.node

        if dx == dy and xf.val != yf.val:
            return True
        return False

解法三

哈希+BFS

def isCousins3(self, root, x, y):
        queue, hm = [(root, None)], {}  # BFS, 每层扫描完后考察是否找到其中一个点(若找到则跳出)
        while queue and not (x in hm or y in hm):
            n = len(queue)
            for i in range(n):  # 扫描每一层
                node, parent = queue.pop(0)
                if node:  # 把当前节点作为父节点信息往下传
                    queue += [(node.left, node), (node.right, node)]
                    hm[node.val] = parent  # 直接哈希记录父节点
        return (x in hm and y in hm) and hm[x] != hm[y]  # 同一层且父节点不同