迭代删除二叉树中的节点及其子节点

Question

Example Tree image

给定一棵二叉树和指向树中节点（存在）的指针，假设我们有父指针。我必须找到删除相邻节点和该删除节点的后续相邻节点的迭代次数。这里删除意味着设置一些标志，node -> burn。我不会删除节点。 示例：

         1
       /   \
      2     3
     / \   / \
    4   5 6  7
   /   / 
  8   9
 /
10

树中的给定节点是 4，

每次迭代烧毁的节点

在迭代 1 中：

• 对于节点4：4,8,2（8是子节点，2是4的父节点，这些是4的相邻节点）。

在迭代 2 中：

• 对于节点 8: 10 将被销毁。 （4 已被烧掉）
• 对于节点 2：5 和 1 将被销毁。

这会继续...，因此我必须找到燃烧所有节点所需的迭代次数。

Answer 1

效率不高，但我认为它会起作用：

为要考虑删除的下一个节点维护一个队列。在删除节点的相邻节点之前，检查它们是否已经设置了 burn 标志。

此外，每次从队列中删除项目时：

• 检查是否所有节点都被烧毁（为此你可以维护一个 Hash 访问速度更快）
• 增加迭代次数（这将是您的结果）