javascript - 尝试过的二叉树示例将输出作为一个对象，我怎样才能将这个对象值放入一个数组中以处理进一步的问题

Question

问题陈述给你一棵树，有 N 个节点，根节点为 1。N 个节点中的每一个都有一些与之相关的特殊数字 Se。每个节点也有一定的权力。树的每个节点的幂定义为该节点(包括该节点)的子树中重节点的数量。重节点是其特殊数的约数和为3的倍数的节点。给你Q个查询

有两种类型的查询:

• 类型1:更新特殊节点数。
• 类型 2:讲述某个节点的力量。

输入格式

第一行:两个空格分隔的整数 N 和 Q 分别表示树中的节点数和查询数。接下来的 N-1 行中的每一行:两个空格分隔的整数 U 和 V 表示它们之间有一条边。下一行:N个空格分隔的整数，其中i表示与节点i相关的特殊数字。接下来Q行的第一个整数是T(查询类型)。如果T为1，则后跟2个整数X和Y，表示节点X的特殊数S更新为Y 如果T为2，则后跟单个整数X

输出格式

对于类型 2 的每个查询，输出给定节点 X 的功率。每个查询的答案都应该换行

我的问题陈述的解释基本上，我们有一个带有编号节点 (Si) 的树。其中一些节点可能有子节点(因为它是一棵树)。

问题要求的是找到节点的“功率”，其中功率定义为其子节点中“重节点”的数量。

“重节点”定义为 Si 的除数之和为 3 的倍数的节点。

这里有一堆信息我们需要计算:

• 对于给定的节点，我们需要获取它的所有子节点
• 对于每个子节点，我们需要找到该节点编号的除数
• 我们需要对除数求和并确定它是否是 3 的倍数

给定样本输入和输出，如

示例输入

5 5 

1 2 

1 3

3 4 

3 5

16 8 17 3 18

2 1

2 3 

1 3 7

2 1

2 3 

示例输出

3

2 

2

1 

我试过的代码

function BinarySearchTree() {
  this.root = null;
}

BinarySearchTree.prototype.insertNode = function (val) {
  var node = {
    data : val, 
    left : null, 
    right : null
  };

  var currentNode;

  if (!this.root) {
    this.root = node;
  } else {
    currentNode = this.root;
    while (currentNode) {
      if (val < currentNode.data) {
          if (!currentNode.left) {
            currentNode.left = node;
            break;
          } else {
            currentNode = currentNode.left;
          }
      } else if (val > currentNode.data) {
        if (!currentNode.right) {
          currentNode.right = node;
          break;
        } else {
          currentNode = currentNode.right;
        }
      } else {
        break;
      }
    }    
  }
};

var BST = new BinarySearchTree();

BST.insertNode(16);
BST.insertNode(8);
BST.insertNode(17);
BST.insertNode(3);
BST.insertNode(18);

console.log(BST);

我的输出

BinarySearchTree {
  root:
   { data: 16,
     left: { data: 8, left: [Object], right: null },
     right: { data: 17, left: null, right: [Object] } } }

现在我想像 [16,8,17,3,18] 这样的数组传递这些数据

并且想要找到每个节点的除数并且必须检查除数是否可以被 3 整除。如何做到这一点？

这是正确的做法吗？

Answer 1

我已经用以下方法尝试了这个问题:

a) 对于获取每个特殊数字的因子总和，使用 Sieve 方法预先计算，如果总和 % 3 == 0，则为该节点放置 1。
b) 应用遍历方法 (dfs) 得到下面所有节点的总和，包括该节点。复杂度为 O(n)。
c) 对于类型 2 的每个查询:我可以在 O(1) 中给出答案。但是对于 Type 1 : query ，我的代码在最坏的情况下采用 O(n) 复杂性。因为对于每个节点，它正在更新每个连续父节点的计数。因此，复杂性达到 O(q*n)，这远远超过因为查询是 10^6 阶而 n 是 10^6 阶。