前端刷题路-Day47：二叉树的堂兄弟节点（题号993）-一一网

这是我参与更文挑战的第11天，活动详情查看：更文挑战

二叉树的堂兄弟节点（题号993）

题目

在二叉树中，根节点位于深度 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
复制代码

提示：

二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为 1 到 100 的整数。

链接

leetcode-cn.com/problems/co…

解释

这题啊，是笔者想多了。

本以为有多硬的方法，结果就是简单的遍历全部数组，找到每个元素的层级并和x、y进行对比。

这就完事了，而且无所谓遍历的顺序，前序、中序、后序都可以，唯一需要记住的事情就是在遍历的过程中和x、y对比，并且记住层级。

自己的答案（BFS）

var isCousins = function (root, x, y) {
  var xParent = xLevel = xFound = null
      yParent = yLevel = yFound = null
      stack = [[root, 0]]
  function findXY(node, parent, level) {
    if (node.val === x) {
      [xParent, xLevel, xFound] = [parent, level, true]
    }
    if (node.val === y) {
      [yParent, yLevel, yFound] = [parent, level, true]
    }
  }
  findXY(root, null, 0)
  while (stack.length) {
    const [node, level] = stack.pop()
    if (node.left) {
      stack.unshift([node.left, level + 1])
      findXY(node.left, node.val, level + 1)
    }
    if (node.right) {
      stack.unshift([node.right, level + 1])
      findXY(node.right, node.val, level + 1)
    }
    if (xFound && yFound) break
  }
  return xLevel === yLevel && xParent !== yParent
};
复制代码

没啥可说的，就是简单的广度优先搜索，在搜索过程中调用findXY方法来获取比较的结果。

自己的答案（DFS）

var isCousins = function (root, x, y) {
  var xParent = xLevel = xFound = null
      yParent = yLevel = yFound = null
      stack = [[root, 0]]
  function findXY(node, parent, level) {
    if (node.val === x) {
      [xParent, xLevel, xFound] = [parent, level, true]
    }
    if (node.val === y) {
      [yParent, yLevel, yFound] = [parent, level, true]
    }
  }
  function DFS(node, parent, level) {
    if (!node) return
    findXY(node, parent, level + 1)
    if (xFound && yFound) return
    if (node.left) {
      DFS(node.left, node.val, level + 1)
    }
    if (xFound && yFound) return
    if (node.right) {
      DFS(node.right, node.val, level + 1)
    }
  }
  DFS(root, 0, null)
  return xLevel === yLevel && xParent !== yParent
};
复制代码

同理可得，也是简单的深度优先搜索，别的没啥。

自己的答案（DFS+Map）

上面这两种方法还是有点复杂的，虽然在遍历到x和y就停止了，每次判断确实比较麻烦，而且xParent、xLevel和xFound这些个变量确实太多了，这里可以利用Map或者对象来存储每个节点的相关信息，在遍历完所有的节点后取出x和y节点，再拿它们的值互相对比就完事了。

var isCousins = function(root, x, y) {
  var map = new Map()
  function DFS(node, level = 0, parent = null) {
    if (!node) return
    map.set(node.val, { level, parent })
    DFS(node.left, level + 1, node.val)
    DFS(node.right, level + 1, node.val)
  }
  DFS(root)
  return map.get(x).level === map.get(y).level && map.get(x).parent !== map.get(y).parent
};
复制代码

看吧，代码量确实很少，使用广度优先搜索也差不多，反正比上面的两种方法少了很多。

缺点也很明显：