993.二叉树的堂兄弟节点

链接：993.二叉树的堂兄弟节点
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：72ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：dfs。

function isCousins(root: TreeNode | null, x: number, y: number): boolean {
  const map = new Map<number, { parent: TreeNode | null; level: number }>();
  dfs();
  const xNode = map.get(x)!;
  const yNode = map.get(y)!;
  return xNode.level === yNode.level && xNode.parent !== yNode.parent;
  function dfs(node: TreeNode | null = root, level = 0, parent: TreeNode | null = null) {
    if (node === null) return;
    map.set(node.val, {
      parent,
      level,
    });
    dfs(node.left, level + 1, node);
    dfs(node.right, level + 1, node);
  }
}

题解 2 - python

• 编辑时间：2024-02-08
• 执行用时：41ms
• 内存消耗：16.5MB
• 编程语言：python
• 解法介绍：遍历记录父亲和level。

class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        map = {}
        xlevel = ylevel = 0
        xnode, ynode = None, None
        def dfs(node: Optional[TreeNode], level = 0):
            nonlocal xnode, ynode, xlevel, ylevel
            if not node: return
            if node.val == x:
                xnode = node
                xlevel = level
            if node.val == y:
                ynode = node
                ylevel = level
            if node.left:
                map[node.left] = node
                dfs(node.left, level + 1)
            if node.right:
                map[node.right] = node
                dfs(node.right, level + 1)
        dfs(root)
        if xlevel != ylevel: return False
        if map[xnode] == map[ynode]: return False
        return True

题解 3 - typescript

• 编辑时间：2021-05-17
• 执行用时：116ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：生成节点的继承链进行比较。

function isCousins(root: TreeNode | null, x: number, y: number): boolean {
  if (root === null) return false;
  const findGrandParent = (
    val: number,
    queue: TreeNode[],
    node: TreeNode | null = root
  ): boolean => {
    if (node === null) return false;
    queue.unshift(node);
    if (node.val === val) return true;
    if (findGrandParent(val, queue, node.left)) return true;
    if (findGrandParent(val, queue, node.right)) return true;
    queue.shift();
    return false;
  };
  const queueX: TreeNode[] = [];
  findGrandParent(x, queueX);
  const queueY: TreeNode[] = [];
  findGrandParent(y, queueY);
  if (queueX.length < 3 || queueY.length < 3) return false;
  return queueX[1] !== queueY[1] && queueX.length === queueY.length;
}