从目标节点开始烧毁二叉树

什么是二叉树？

二叉树是一种泛型树，其中一个节点最多可以有两个子节点。我们给出了一个二叉树和一个目标节点。我们必须从目标节点开始燃烧二叉树，并打印每个级别上燃烧的节点。

燃烧意味着在时间 = 0 时目标节点将被燃烧，然后其父节点和子节点将被燃烧。

例如

第 0 级：燃烧的节点是 5。

第 1 级：燃烧的节点是 2 和 7。

第 2 级：燃烧的节点是 1、4 和 9。

第 3 级：燃烧的节点是 3。

第 4 级：燃烧的节点是 6。

第 5 级：燃烧的节点是 8。

方法 1

在这种方法中，我们的第一个任务是找到目标节点。所以我们会递归地搜索目标节点。找到目标节点后，我们将打印该节点，然后将它的左子节点和右子节点添加到队列中。

对于每个节点，我们将为其左子树和右子树调用递归函数。如果递归函数返回 1，则表示在该子树中找到了目标节点，然后我们将打印队列中的元素，然后打印当前节点。

在主函数中，在此递归调用之后，我们将通过检查队列大小来检查是否还有剩余节点。我们将打印队列中的元素。

Java 代码

输出

时间复杂度：O(N)，其中 N 是节点数。

空间复杂度：O(N) 用于队列。

方法 2

第二种方法是将给定的二叉树转换为无向图。然后，在将树转换为图之后，我们将使用 BFS 方法来燃烧节点。

对于每个节点，我们都有它的子节点和父节点，所以我们将父节点和子节点转换为任何特定节点的邻居节点。

我们将使用队列数据结构来获得给定图的广度优先搜索。

我们将使用一个哈希表，其中键是节点，值是节点列表，该列表包含每个节点的邻居列表，我们可以以常量时间访问。

Java 代码

输出

时间复杂度：O(N)，其中 N 是节点数。

空间复杂度：O(N)

注意：此方法存在局限性。此方法会更改给定的数据结构，因此数据丢失和数据复杂性的可能性很高，因此不应首选此方法。