“This is the 27th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

993. Cousin nodes of binary trees

The title

In a binary tree, the root node is at depth 0, and the children of each node of depth K are 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

Input: root = [1,2,3,4], x = 4, y = 3 output: falseCopy the code

Example 2

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 output: trueCopy the code

Answer key

Intuitive DFS

  • Depth-first traversal of the binary tree, using variables xLevel, yLevelxLevel, yLevelxLevel, yLevelxLevel, yLevel to record the hierarchy of nodes X,yx, yx,y
  • The two nodes in the binary tree have the same depth but different parent nodes. Therefore, the variable signsignSign is needed to maintain whether the two nodes have the same parent node
  • The node decides whether x,y, x, yx,y is a self node, and this logic is also expressed in a long code so it’s ugly to write

Edit the code as follows:

var isCousins = function (root, x, y) {
  let xLevel = -1
  let yLevel = -1
  let sign = 1
  dfs(root, 0)
  //console.log('xLevel',xLevel,yLevel)
  if (sign) {
    return xLevel === yLevel
  } else {
    return false
  }
  function dfs(node, level) {
    if (node === null) return
    if (node.val === x) xLevel = level
    if (node.val === y) yLevel = level
    if (
      node &&
      node.left &&
      node.left.val === x &&
      node &&
      node.right &&
      node.right.val === y
    ) {
      sign = 0
      return
    }

    if (
      node &&
      node.left &&
      node.left.val === y &&
      node &&
      node.right &&
      node.right.val === x
    ) {
      sign = 0
      return
    }

    dfs(node.left, level + 1)
    dfs(node.right, level + 1)}}Copy the code

Although the above code is more intuitive, but too long, programmers should simplify their code;

Optimized code:

var isCousins = function (root, x, y) {
  let xLevel = -1
  let yLevel = -1
  let xParent = null
  let yParent = null
  dfs(root, 0.null)
  returnxLevel === yLevel && xParent ! == yParentfunction dfs(node, level, parent) {
    if (node === null) return
    if (node.val === x) {
      xLevel = level
      xParent = parent
    }
    if (node.val === y) {
      yLevel = level
      yParent = parent
    }

    dfs(node.left, level + 1, node)
    dfs(node.right, level + 1, node)
  }
}
Copy the code

After optimization, the code still has four extra variables to save data, which is still a little awkward. Can we optimize it again?

Yes, when we recurse, we deal with the hierarchy of the parent, and we return it

var isCousins = function (root, x, y) {
  return dfs(root, 0) = = = -1
  function dfs(node, level) {
    if(! node)return 0
    if (node.val == x || node.val == y) return level
    const l = dfs(node.left, level + 1)
    const r = dfs(node.right, level + 1)
    if (l < 0) return l
    if (r < 0) return r
    if (l > 0 && r > 0) {
      if(l == r && l ! = level +1) return -1
      else return -2
    }
    if (l > 0) return l
    if (r > 0) return r
    return 0}}Copy the code