In a binary tree, the root node is located at depth 0, and the child nodes of each node with depth K are located at depth K +1.

If two nodes in a binary tree have the same depth but different parents, they are a pair of Cousins.

We give the root node of a binary tree with unique values, root, and the values x and y of two different nodes in the tree.

Returns true only if the nodes corresponding to the values x and y are Cousins. Otherwise, return false.

Example 1:

Example 2:

The original address

There are two key points to determine whether a cousin node is a cousin node. So you can look for x and y and record the corresponding depth and parent nodes as you traverse the entire binary tree.

Solution 1: depth first traversal

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}* /
var isCousins = function(root, x, y) {
  var x_found = false, x_depth = 0, x_parent = null;
  var y_found = false, y_depth = 0, y_parent = null;
  var dfs = (node, parent, depth) = > {
    if(! node)return
    if (node.val === x) {
      [x_found, x_depth, x_parent] = [true, depth, parent]
    }
    if (node.val === y) {
      [y_found, y_depth, y_parent] = [true, depth, parent]
    }

    if (x_found && y_found) return

    if (node.left) {
      dfs(node.left, node, depth + 1)}if (x_found && y_found) return

    if (node.right) {
      dfs(node.right, node, depth + 1)
    }
  }
  dfs(root, null.0)
  if (x_found && y_found) {
    if(x_depth === y_depth && x_parent ! == y_parent) {return true}}return false
};
Copy the code

Solution two: breadth-first traversal

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}* /
var isCousins = function(root, x, y) {
  var x_found = false, x_depth = 0, x_parent = null;
  var y_found = false, y_depth = 0, y_parent = null;
  // Check whether the node is x or y
  var update = (node, parent, depth) = > {
    if (node.val === x) {
      [x_found, x_depth, x_parent] = [true, depth, parent]
    }
    if (node.val === y) {
      [y_found, y_depth, y_parent] = [true, depth, parent]
    }
  }
  var dp = [[root, 0]]
  update(root, null.0)
  while (dp.length) {
    var [node, depth] = dp.shift()
    if (node.left) {
      update(node.left, node, depth + 1)
      dp.push([node.left, depth + 1])}if (x_found && y_found) break
    if (node.right) {
      update(node.right, node, depth + 1)
      dp.push([node.right, depth + 1])}if (x_found && y_found) break
  }
  if (x_found && y_found) {
    if(x_depth === y_depth && x_parent ! == y_parent) {return true}}return false
};
Copy the code