Lstmxx的空间

1361. 验证二叉树

二叉树上有 n  个节点，按从  0  到 n - 1  编号，其中节点  i  的两个子节点分别是  leftChild[i]  和  rightChild[i]。

只有 所有 节点能够形成且 只 形成 一颗   有效的二叉树时，返回  true；否则返回 false。

如果节点  i  没有左子节点，那么  leftChild[i]  就等于  -1。右子节点也符合该规则。

注意：节点没有值，本问题中仅仅使用节点编号。

链接

/**
 * @param {number} n
 * @param {number[]} leftChild
 * @param {number[]} rightChild
 * @return {boolean}
 */
var validateBinaryTreeNodes = function (n, leftChild, rightChild) {
  const inDegree = new Array(n).fill(0);

  // 计算入度, 每出现一次入度 + 1
  for (let i = 0; i < n; i++) {
    const l = leftChild[i];
    const r = rightChild[i];
    if (l !== -1) {
      inDegree[l] += 1;
    }
    if (r !== -1) {
      inDegree[r] += 1;
    }
  }

  let count = 0;
  if (inDegree.filter((deg) => deg === 0).length !== 1) {
    return false;
  } else {
    const que = [inDegree.indexOf(0)];
    while (que.length) {
      const node = que.shift();
      count += 1;
      if (count > n) {
        break;
      }
      if (leftChild[node] !== -1) {
        que.push(leftChild[node]);
      }
      if (rightChild[node] !== -1) {
        que.push(rightChild[node]);
      }
    }
    return n === count;
  }
};